概要

会議室の利用可能時間 \(0\) から \(T\) の中で、\(N\) 件の予約が入っていないときの最も長い連続した空き時間を求める問題です。

考察

重要な気づき

予約と予約の間の隙間が「空き時間」になります。空き時間は以下の3種類に分類できます：

1. 時刻 \(0\) から最初の予約が始まるまで
2. ある予約が終わってから次の予約が始まるまで（予約間の隙間）
3. 最後の予約が終わってから時刻 \(T\) まで

具体例で考える

例えば \(T = 20\) で、予約が \((2, 5), (10, 15), (7, 9)\) の3件あるとします。

開始時刻でソートすると \((2, 5), (7, 9), (10, 15)\) となります。

時刻: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
     [空き][予約1 ][空][予約2][予約3      ][空き時間         ]

空き時間は： - 時刻 \(0\) ～ \(2\)：長さ \(2\) - 時刻 \(5\) ～ \(7\)：長さ \(2\) - 時刻 \(9\) ～ \(10\)：長さ \(1\) - 時刻 \(15\) ～ \(20\)：長さ \(5\) ← 最長！

なぜソートが必要か

予約は入力順に並んでいるとは限りません。時系列で空き時間を調べるために、開始時刻でソートする必要があります。

アルゴリズム

1. 入力を受け取り、すべての予約を配列に格納する
2. 開始時刻でソートする
3. 3種類の空き時間を順番に計算し、最大値を更新する
   • 最初の空き時間：reservations[0][0] - 0（最初の予約の開始時刻）
   • 予約間の空き時間：reservations[i][0] - reservations[i-1][1]（\(i\) 番目の予約の開始時刻 - \((i-1)\) 番目の予約の終了時刻）
   • 最後の空き時間：T - reservations[-1][1]（\(T\) - 最後の予約の終了時刻）
4. 最大値を出力する

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • 空き時間の計算に \(O(N)\)
• 空間計算量: \(O(N)\)
  • 予約を格納する配列に \(O(N)\)

実装のポイント

1. ソートを忘れない：入力が時刻順とは限らないため、必ず開始時刻でソートしましょう。

2. 端の処理を忘れない：予約間の空き時間だけでなく、「最初の予約の前」と「最後の予約の後」の空き時間も忘れずに確認する必要があります。

3. タプルのソート：Pythonでは (開始時刻, 終了時刻) のタプルをソートすると、自動的に開始時刻でソートされます（第1要素を優先）。

4. インデックスに注意：reservations[i][0] は \(i\) 番目の予約の開始時刻、reservations[i][1] は終了時刻を表します。

   ソースコード

def solve():
    N, T = map(int, input().split())
    
    reservations = []
    for _ in range(N):
        s, e = map(int, input().split())
        reservations.append((s, e))
    
    # 開始時刻でソート
    reservations.sort()
    
    max_free_time = 0
    
    # 最初の予約が始まる前の空き時間
    max_free_time = max(max_free_time, reservations[0][0])
    
    # 予約と予約の間の空き時間
    for i in range(1, N):
        free_time = reservations[i][0] - reservations[i-1][1]
        max_free_time = max(max_free_time, free_time)
    
    # 最後の予約が終わった後の空き時間
    max_free_time = max(max_free_time, T - reservations[-1][1])
    
    print(max_free_time)

solve()

---

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