概要

参加者の希望出発時刻に基づいて、希望時刻の差が \(K\) 以内であれば同じバスに乗れるとき、全員を載せるのに必要なバスの最小台数を求めます。

考察

この問題では、希望出発時刻のリスト \(T_1, T_2, \ldots, T_N\) が与えられ、差が \(K\) 以内の参加者を同じグループ（バス）にまとめることで、グループ数を最小化する必要があります。

素朴な方法として、すべての組み合わせを試してグループ分けを試みると、計算量が非常に大きくなり、間に合いません（TLE）。また、貪欲に「入れられるだけ入れる」ような戦略が必要です。

ここで重要な観察があります：
希望出発時刻を昇順にソートしたとき、連続した範囲に含まれる参加者たちは、同じバスに乗せられる可能性がある。

つまり、ソート後に前から順番に見ていき、「現在のバスに乗せられない人（希望時刻の差が \(K\) を超える人）が現れたら、新しいバスを用意する」という貪欲法が有効です。

例えば、入力例：

N = 5, K = 3
T = [1, 2, 8, 9, 10]

これをソートしても変わらず、最初のバスには時刻 1〜4 までの人を入れられます（2 まではOKだが 8 はNG）。よって、時刻 1, 2 は一台のバス、8, 9, 10 はもう一台のバス → 合計2台。

このように、ソートして前から見ていくことで最適解が得られます。

アルゴリズム

1. 希望出発時刻のリスト \(T\) を昇順にソートします。
2. 最初の参加者を最初のバスの基準時刻（start）とします。
3. 次の参加者から順に、その人の希望時刻が start + K 以内であれば同じバスに乗せます。
4. start + K を超える人が現れた時点で、新しいバスを用意し、その人の希望時刻を新たな start とします。
5. 全員を処理するまでこれを繰り返し、使用したバスの台数をカウントします。

計算量

• 時間計算量: \(O(N \log N)\) （ソートが支配的）
• 空間計算量: \(O(1)\) （入力の配列除く）

実装のポイント

• ソートを行うことを忘れないこと。
• 最初の参加者を基準としてスタートするので、初期値の設定に注意。
• ループ内で「現在のバスに乗せられるか？」を判定し、乗せられない場合は新しいバスをカウントアップすること。

## ソースコード

```python
N, K = map(int, input().split())
T = list(map(int, input().split()))

T.sort()

count = 1
start = T[0]

for i in range(1, N):
    if T[i] - start > K:
        count += 1
        start = T[i]

print(count)

この解説は qwen3-coder-480b によって生成されました。