概要

希望出発時刻 \(T_i\) を持つ \(N\) 人を、「同じバス内の任意の2人の時刻差が \(K\) 以下」になるように班分けし、必要なバスの最小台数を求めます。

考察

重要な気づき

同じバスに乗る条件は「バス内の最大時刻 − 最小時刻 \(\le K\)」と言い換えられます。
なぜなら、あるグループ内で最小を \(a\)、最大を \(b\) とすると、任意の2人の差の最大値は \(b-a\) であり、これが \(K\) 以下なら全てのペアが条件を満たすからです。

よって、参加者の時刻を昇順に並べたとき、1台のバスに乗る人たちは連続区間（連続した並び）として取れるのが最適になります。途中を飛ばして入れる必要はありません（飛ばした人はその間の時刻なので、条件を満たすなら一緒に入れてよい）。

素朴なアプローチが難しい理由

• 「誰と誰を同じバスにするか」を全探索すると組合せが爆発します。
• 各人について「同じバスに入れられる最大集合」を探索するような方法も、最悪 \(O(N^2)\) となり \(N \le 2\times 10^5\) では間に合いません。

どう解決するか

時刻をソートし、一番早い未割当の人を起点にして、条件 \(T[j]-T[i]\le K\) を満たす限り後ろの人を同じバスに詰めるのが最適です。
こうすると、そのバスは「起点時刻から \(K\) 以内にいる人」を最大限乗せるため、残りの人を減らせてバス台数を最小化できます。

具体例： - \(T=[1,2,3,7,8],\ K=2\)（ソート済み） - 最初の人 \(1\) を起点に、\(1+2=3\) まで乗れるので \(\{1,2,3\}\) で1台 - 次に \(7\) を起点に、\(7+2=9\) まで乗れるので \(\{7,8\}\) で1台
→ 合計2台

アルゴリズム

1. 配列 \(T\) を昇順にソートする。
2. ポインタ \(i\) を先頭に置き、未割当が残っている間繰り返す：
   • 新しいバスを1台追加する。
   • そのバスの最小時刻を start = T[i] とする。
   • \(i\) を進めながら、T[i] - start <= K を満たす限り同じバスに乗せる（＝\(i\) を増やす）。
3. バスを追加した回数を出力する。

この方法は「各バスが取りうる範囲を最大限詰める」貪欲法で、ソート後の並びでは区間分割問題になっているため最適になります。

計算量

• 時間計算量: ソートに \(O(N\log N)\)、走査は \(O(N)\) なので合計 \(O(N\log N)\)
• 空間計算量: ソート済み配列などで \(O(N)\)

実装のポイント

• 条件は「同じバス内の任意の2人」ですが、ソート後は「最小（先頭）との差」だけ見れば十分で、T[i] - start <= K の判定で済みます。

• \(N\) が大きいので、入力は sys.stdin.buffer.read() を使うと高速です。

• 走査は二重ループに見えますが、ポインタ \(i\) は全体で \(0 \to N\) まで一度しか進まないため、走査部分は実質 \(O(N)\) です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    T = data[2:2+N]
    T.sort()

    buses = 0
    i = 0
    while i < N:
        buses += 1
        start = T[i]
        i += 1
        while i < N and T[i] - start <= K:
            i += 1

    print(buses)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。