Matryoshkas (Codeforces 1790D)
Tags: Greedy, sortings

Matryoshka is a wooden toy in the form of a painted doll, inside which you can put a similar doll of a smaller size.A set of nesting dolls contains one or more nesting dolls, their sizes are consecutive positive integers. Thus, a set of nesting dolls is described by two numbers: $$$s$$$ — the size of a smallest nesting doll in a set and $$$m$$$ — the number of dolls in a set. In other words, the set contains sizes of $$$s, s + 1, \dots, s + m - 1$$$ for some integer $$$s$$$ and $$$m$$$ ($$$s,m > 0$$$).You had one or more sets of nesting dolls. Recently, you found that someone mixed all your sets in one and recorded a sequence of doll sizes — integers $$$a_1, a_2, \dots, a_n$$$.You do not remember how many sets you had, so you want to find the minimum number of sets that you could initially have.For example, if a given sequence is $$$a=[2, 2, 3, 4, 3, 1]$$$. Initially, there could be $$$2$$$ sets:   the first set consisting of $$$4$$$ nesting dolls with sizes $$$[1, 2, 3, 4]$$$;  a second set consisting of $$$2$$$ nesting dolls with sizes $$$[2, 3]$$$. According to a given sequence of sizes of nesting dolls $$$a_1, a_2, \dots, a_n$$$, determine the minimum number of nesting dolls that can make this sequence.Each set is completely used, so all its nesting dolls are used. Each element of a given sequence must correspond to exactly one doll from some set.

Input: The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The description of the test cases follows.The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the total number of matryoshkas that were in all sets.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)  — the sizes of the matryoshkas. It is guaranteed that the sum of values of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output: For each test case, print one integer $$$k$$$ — the minimum possible number of matryoshkas sets.

Note: The first test case is described in the problem statement.In the second test case, all matryoshkas could be part of the same set with minimum size $$$s=7$$$.In the third test case, each matryoshka represents a separate set.

Sample Inputs:
10
6
2 2 3 4 3 1
5
11 8 7 10 9
6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
8
1 1 4 4 2 3 2 3
6
1 2 3 2 3 4
7
10 11 11 12 12 13 13
7
8 8 9 9 10 10 11
8
4 14 5 15 6 16 7 17
8
5 15 6 14 8 12 9 11
5
4 2 2 3 4

Sample Outputs:
2
1
6
2
2
2
2
2
4
3

Solution (Python):
for s in [*open(0)][2::2]:
    r = p = l = 0
    for x in sorted(map(int, s.split())):
        if x > p:
            m = l * (x - p < 2)
            l = 0
        l += 1
        r += l > m
        p = x
    print(r)

Solution (Python):
for z in [*open(0)][2::2]:
    q = e = l = 0
    for d in sorted(map(int, z.split())):
        if d > e:
            m = l * (d - e < 2)
            l = 0
        l += 1
        q += l > m
        e = d
    print(q)

Solution (Python):
t = int(input())
for _t in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    rowCount = 0
    freeTails = 0
    lastNumBefore = -1000
    num = None
    numCount = 0
    for i in range(n):
        if num is None:
            num = a[i]
            numCount = 1
        elif a[i] == num:
            numCount += 1
        else:
            if num == lastNumBefore + 1:
                if numCount > freeTails:
                    rowCount += numCount - freeTails
            else:
                rowCount += numCount
            lastNumBefore = num
            freeTails = numCount
            num = a[i]
            numCount = 1
    if num == lastNumBefore + 1:
        if numCount > freeTails:
            rowCount += numCount - freeTails
    else:
        rowCount += numCount
    print(rowCount)