Overview

This is a problem of partitioning \(N\) cards into sets of consecutive integers (consecutive groups) while minimizing the number of groups. It can be solved by sorting the cards and counting the positions where consecutive numbers are broken.

Analysis

Key Observations

First, let’s confirm what a consecutive group is. For example: - \(\{3, 4, 5\}\) is a consecutive group (all differences are \(1\)) - \(\{2, 4, 5\}\) is not a consecutive group (the difference between \(2\) and \(4\) is \(2\))

Point 1: All card values are distinct (\(A_i \neq A_j\)), so we don’t need to consider cards with the same value.

Point 2: To minimize the number of groups, we want to put as many cards as possible into a single group. In other words, all consecutive numbers should be placed in the same group.

Thinking Through a Concrete Example

Consider the input \(\{3, 1, 5, 2, 8, 7\}\).

After sorting, we get \(\{1, 2, 3, 5, 7, 8\}\).

Looking at the differences between adjacent elements: - \(2 - 1 = 1\) → consecutive ✓ - \(3 - 2 = 1\) → consecutive ✓ - \(5 - 3 = 2\) → not consecutive ✗ (a group boundary occurs here) - \(7 - 5 = 2\) → not consecutive ✗ (a group boundary occurs here) - \(8 - 7 = 1\) → consecutive ✓

As a result, the cards are divided into 3 groups: \(\{1, 2, 3\}\), \(\{5\}\), \(\{7, 8\}\).

Why Sort?

A consecutive group is defined as “a set where, when arranged in ascending order, all adjacent differences are \(1\).” Therefore, sorting first and then checking for consecutiveness is a natural approach.

Algorithm

1. Sort array \(A\) in ascending order
2. Initialize the group count to \(1\) (at least one group is needed)
3. Compare adjacent elements in order; if the difference is not \(1\), increment the group count by \(1\)
4. Output the final group count

Intuitive understanding: Scanning the sorted array from left to right, the number of groups equals “the number of times consecutiveness is broken \(+ 1\).”

After sorting: [1, 2, 3, 5, 7, 8]
                ├─consecutive─┤  │  ├consecutive┤
                Group 1        G2  Group 3

Complexity

• Time complexity: \(O(N \log N)\)

  • Sorting takes \(O(N \log N)\)
  • Scanning the array once takes \(O(N)\)
  • Overall, \(O(N \log N)\) dominates

• Space complexity: \(O(N)\)

  • Storing the input array takes \(O(N)\)
  • Additional space used for sorting (Python’s sort uses \(O(N)\))

Implementation Notes

1. Initialize to 1: As long as the array is not empty, at least one group exists. Since the loop counts “positions where groups split,” we initialize the count to 1.

2. Loop range: Use range(1, N) and compare index \(i\) with \(i-1\). Be careful that starting from \(i = 0\) would reference \(A[-1]\).

3. Case \(N = 1\): The loop does not execute, and \(1\) is output as is. This is correct behavior (one card forms one group).

   Source Code

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # ソートする
    A.sort()
    
    # 連番グループの数をカウント
    # 隣り合う要素の差が1でない箇所でグループが分かれる
    groups = 1
    for i in range(1, N):
        if A[i] - A[i-1] != 1:
            groups += 1
    
    print(groups)

solve()

---

This editorial was generated by claude4.5opus.