Overview

Given a sequence of integers, we want to divide them into groups of consecutive numbers (consecutive-number groups) and find the minimum number of groups required.

Approach

The goal of this problem is to partition the numbers written on cards into several “sequences of consecutive integers.” For example, if the card numbers are \(\{3, 5, 4, 7, 6\}\), they are all consecutive, so they can form a single group. On the other hand, if we have \(\{1, 3, 5\}\) where the numbers are non-consecutive, each must be placed in a separate group.

A straightforward approach is to greedily connect consecutive numbers together. However, if we simply process the array in its original order, we might miss consecutive relationships when the input is unsorted. Therefore, we first sort the card numbers and process them in ascending order.

Additionally, to handle cases where the same number appears multiple times (though this doesn’t occur under the current constraints) or to manage the data efficiently from an algorithmic standpoint, it is effective to use a dictionary that tracks the occurrence count of each number.

The key insight of this problem is that by greedily connecting consecutive numbers as much as possible into a single group, we can minimize the number of groups. Specifically, if a number \(x\) has not been used yet, we extend a consecutive sequence \(x, x+1, x+2, \ldots\) as far as possible, and that becomes one group. By repeating this process, we can optimally partition the entire set.

Algorithm

1. Sort the integer sequence \(A\) written on the cards.
2. Record the occurrence count of each number (since there are no duplicates in this problem, each appears exactly once).
3. Process the numbers from smallest to largest, extending consecutive sequences as far as possible:
   • If the current number \(num\) is still available, consecutively use \(num+1, num+2, \ldots\) in order, stopping when the sequence breaks.
   • This series of operations completes one consecutive-number group.
4. Perform the above for all numbers and count the total number of groups created.

Example

Sample input:

5
3 5 4 7 6

• After sorting: \(\{3, 4, 5, 6, 7\}\)
• Starting from 3, we can use consecutive numbers up to 7 → 1 group
• Result: The number of groups is \(1\)

Another example:

4
1 3 5 7

• None of them are consecutive → Each number forms its own group
• Result: The number of groups is \(4\)

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (dictionary for recording occurrence counts)

Implementation Notes

• Use sys.stdin.read for fast input reading.
• Manage occurrence counts of each number with defaultdict to avoid errors when accessing non-existent keys.
• By processing numbers in sorted order, we can reliably determine consecutiveness.
• By looping until each number is used up and progressively consuming consecutive numbers, we greedily construct optimal groups.

## Source Code

```python
import sys
from collections import defaultdict

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    # Sort the array to process in order
    A.sort()
    
    # Dictionary to count how many times each number appears
    count = defaultdict(int)
    for num in A:
        count[num] += 1
    
    groups = 0
    
    # Process each unique number in sorted order
    for num in sorted(count.keys()):
        # While there are still cards with this number
        while count[num] > 0:
            # Start a new group
            current = num
            count[current] -= 1
            # Extend the group as far as possible
            while count[current + 1] > 0:
                current += 1
                count[current] -= 1
            groups += 1
    
    print(groups)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.