Overview

Given \(N\) cards (all with distinct integers), we want to divide them into groups such that each group forms a “sequence of consecutive integers.” The goal is to find the minimum number of groups required.

Analysis

A “consecutive number group” is a set where, when the contained numbers are sorted in ascending order, the difference between every pair of adjacent numbers is exactly \(1\). To satisfy this condition, the values within the same group must be consecutive integers.

The key observation is as follows:

• When the card values are sorted in ascending order, cards can be placed in the same consecutive group only within “intervals where the difference between adjacent values is \(1\).”
• Conversely, when sorted in ascending order, any place where the difference is not \(1\) (a gap) must be a boundary between groups. This is because the intermediate integers do not exist, so placing them in the same group would violate the “difference of \(1\)” condition.

Therefore, - Minimum number of groups = (number of positions where the difference is not \(1\) when viewed in ascending order) + 1

Naively searching for “which card goes into which group” or trying different groupings by trial and error leads to combinatorial explosion, which is not feasible for \(N \le 2 \times 10^5\). However, with the above observation, the answer is determined simply by “sorting and checking the differences.”

Example: \(A=\{3,5,4,10,11\}\) Sorted in ascending order: \([3,4,5,10,11]\) Differences are \(1,1,5,1\), so there is \(1\) position where the difference is not \(1\) (the \(5\)) → Number of groups is \(1+1=2\) (\(\{3,4,5\}\) and \(\{10,11\}\))

Algorithm

1. Sort the array \(A\) in ascending order.
2. Initialize the group count groups to \(1\) (since \(N \ge 1\), at least one group is needed).
3. For \(i=1\) to \(N-1\), if \(A[i]-A[i-1] \neq 1\), increment groups by \(1\).
4. Output groups.

Complexity

• Time complexity: \(O(N \log N)\) for sorting and \(O(N)\) for the difference check, giving a total of \(O(N \log N)\)
• Space complexity: \(O(N)\) for the sorted array, etc.

Implementation Notes

• \(A_i\) can be up to \(10^9\), but difference calculations can be safely handled with Python’s integers.

• To correctly output \(1\) even when \(N=1\), we initialize with groups = 1.

• Since the input can be large, using sys.stdin.readline ensures stability.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))
    A.sort()
    groups = 1
    for i in range(1, N):
        if A[i] - A[i - 1] != 1:
            groups += 1
    print(groups)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.