概要

与えられた会議室の予約情報から、最も長い連続した空き時間を求めます。

考察

この問題では、会議室の利用時間帯（予約）が複数与えられ、それらの「間」や「前後」に存在する空き時間のうち、最も長いものを求めることになります。

重要な観察点は以下の通りです： - 各予約は重ならないことが保証されているため、単純に開始時刻順にソートすることで、順番に処理できます。 - 空き時間は以下の3パターンに分かれます： 1. 最初の予約が始まる前の時間（時刻 \(0\) 〜 最初の \(S_i\)） 2. ある予約の終了時刻と、次の予約の開始時刻の間（\(E_i\) 〜 \(S_{i+1}\)） 3. 最後の予約が終わった後の時間（最後の \(E_i\) 〜 時刻 \(T\)）

これらの空き時間を順に調べて最大値を取れば答えが得られます。

素朴な方法として、すべての時間（0〜T）をシミュレーションすることは不可能です。なぜなら、\(T\) が最大 \(10^9\) まであり、1秒ずつ調べるとTLE（時間超過）になるからです。

この問題では、予約の数 \(N\) が最大 \(2 \times 10^5\) なので、予約をソートしてその間を調べる方法が現実的です。

アルゴリズム

1. 入力を読み込み、予約を開始時刻 \(S_i\) の順にソートします。
2. 最初の予約以前の空き時間を計算：
   $\(\text{max\_gap} = \max(\text{max\_gap}, S_1 - 0)\)$
3. 各隣接する予約の間の空き時間を計算：
   $\(\text{gap} = S_{i+1} - E_i\)\( \)\(\text{max\_gap} = \max(\text{max\_gap}, \text{gap})\)$
4. 最後の予約以降の空き時間を計算：
   $\(\text{gap} = T - E_N\)\( \)\(\text{max\_gap} = \max(\text{max\_gap}, \text{gap})\)$
5. 最大の \(\text{max\_gap}\) を出力します。

具体例

入力:

3 20
5 9
12 15
0 3

予約を開始時刻順にソートすると：

(0, 3), (5, 9), (12, 15)

空き時間は： - 時刻 0〜3 の前：なし（開始時刻が0） - 3〜5 の間：長さ 2 - 9〜12 の間：長さ 3 - 15〜20 の間：長さ 5

よって、最も長い空き時間は 5 です。

計算量

• 時間計算量: \(O(N \log N)\) （ソートが支配的）
• 空間計算量: \(O(N)\) （予約情報を保存）

実装のポイント

• 入力が多いので sys.stdin.read を使って高速化している

• 予約がない場合（\(N=0\)）は、会議室は丸一日空きなので、\(T\) をそのまま出力する

• ソート後に最初・最後・間の3種類の空き時間を漏れなくチェックする

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    T = int(data[1])
    
    intervals = []
    index = 2
    for _ in range(N):
        s = int(data[index])
        e = int(data[index+1])
        intervals.append((s, e))
        index += 2
    
    # 開始時刻でソート
    intervals.sort()
    
    max_gap = 0
    
    # 最初の予約より前の空き時間
    if intervals:
        max_gap = max(max_gap, intervals[0][0])
    else:
        max_gap = T
    
    # 予約と予約の間の空き時間
    for i in range(1, N):
        prev_end = intervals[i-1][1]
        curr_start = intervals[i][0]
        gap = curr_start - prev_end
        if gap > max_gap:
            max_gap = gap
    
    # 最後の予約より後の空き時間
    if intervals:
        last_end = intervals[-1][1]
        gap = T - last_end
        if gap > max_gap:
            max_gap = gap
    
    print(max_gap)

if __name__ == "__main__":
    main()

---

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