概要

希望出発時刻の差が \(K\) 以下の参加者を同じバスにまとめるとき、必要なバスの最小台数を求める問題です。これは貪欲法（Greedy Algorithm）で効率的に解くことができます。

考察

重要な気づき

同じバスに乗るどの2人の参加者についても時刻差が \(K\) 以下という条件は、言い換えると「そのバスに乗る参加者の中で、最大の時刻と最小の時刻の差が \(K\) 以下」ということになります。

例えば、\(K = 5\) のとき： - 時刻 \([2, 4, 7]\) の3人 → 最大7、最小2、差は5 → OK（同じバスに乗れる） - 時刻 \([2, 4, 8]\) の3人 → 最大8、最小2、差は6 → NG（同じバスに乗れない）

貪欲法が有効な理由

参加者を希望出発時刻でソートすると、以下の貪欲法が最適解を与えます：

1. 最も早い時刻の人から順にバスに乗せていく
2. 1台のバスに、条件を満たす限りなるべく多くの人を乗せる

なぜこれで最適か？ ソート後、あるバスの最初の人（最小時刻）を決めたら、そのバスには「時刻が最小時刻 \(+ K\) 以下」の人を全員乗せるのが最善です。途中で切ってしまうと、後のバスで余計な台数が必要になる可能性があるからです。

具体例

\(N = 5\), \(K = 3\), \(T = [1, 5, 2, 9, 6]\) の場合：

ソート後: \([1, 2, 5, 6, 9]\)

• バス1: 時刻1からスタート → 1, 2（時刻5は \(5-1=4 > K\) なのでNG）
• バス2: 時刻5からスタート → 5, 6（時刻9は \(9-5=4 > K\) なのでNG）
• バス3: 時刻9からスタート → 9

答え: 3台

アルゴリズム

1. 希望出発時刻 \(T\) を昇順にソートする
2. 先頭から順に走査し、新しいバスを作るたびに：
   • そのバスの基準時刻（最小時刻）を記録
   • 「現在の参加者の時刻 - 基準時刻 \(\leq K\)」を満たす限り、参加者を同じバスに乗せる
   • 条件を満たさなくなったら、次のバスを用意
3. 使用したバスの台数を出力

buses = 0
i = 0
while i < N:
    buses += 1
    start_time = T[i]  # このバスの基準時刻
    while i < N and T[i] - start_time <= K:
        i += 1
print(buses)

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • 走査に \(O(N)\)（各参加者を1回ずつ見る）
• 空間計算量: \(O(N)\)
  • 配列 \(T\) の格納に必要

実装のポイント

• ソートが必須: ソートしないと、どの参加者をどのバスに割り当てるべきか判断が難しくなります

• 基準時刻の管理: 各バスの「最初に乗せた人の時刻」を覚えておき、それとの差で判定します

• \(K = 0\) の場合: 同じ時刻の人だけが同じバスに乗れます。このコードは正しく動作します

• オーバーフロー注意: \(T_i\) と \(K\) は最大 \(10^9\) ですが、差を取るだけなので Python では問題ありません

  ソースコード

def solve():
    N, K = map(int, input().split())
    T = list(map(int, input().split()))
    
    # 希望出発時刻でソート
    T.sort()
    
    buses = 0
    i = 0
    
    while i < N:
        # 新しいバスを開始
        buses += 1
        # このバスの基準時刻（最小時刻）
        start_time = T[i]
        # このバスに乗れる参加者を全員乗せる
        # 同じバスに乗る条件: 全員の時刻差がK以下 = 最大時刻 - 最小時刻 <= K
        while i < N and T[i] - start_time <= K:
            i += 1
    
    print(buses)

solve()

---

この解説は claude4.5opus によって生成されました。