概要

会議室の予約区間（使用中の時間）から、時刻 \(0\)〜\(T\) の範囲で最も長い「連続した空き時間（予約のない区間）」の長さを求めます。

考察

重要な点は「空き時間は予約と予約の“間”にしか現れない」ことです。さらに、予約は互いに重ならないので、予約を開始時刻順に並べると空き時間は次の3種類だけになります。

1. \([0, S_{\text{first}})\)（最初の予約より前）
2. \([E_i, S_{i+1})\)（連続する2つの予約の間）
3. \([E_{\text{last}}, T)\)（最後の予約より後）

素朴に「時刻を1つずつ見て空きを数える」ような方法は、\(T\) が最大 \(10^9\) なので現実的ではありません（\(O(T)\) になりTLE）。
そこで、予約区間の情報だけを使って「隣り合う予約の間隔」を調べれば十分です。

具体例： - \(T=10\) - 予約が \((2,3),(5,7)\) のとき
空きは \([0,2)\) 長さ2、\([3,5)\) 長さ2、\([7,10)\) 長さ3
最大は3です。

アルゴリズム

1. 予約区間 \((S_i, E_i)\) を開始時刻 \(S_i\) で昇順ソートする。
2. 答え候補として、最初の予約開始までの空き \(S_{\text{first}}-0\) を入れる。
3. 直前の予約の終了時刻 prev_end を持ちながら、次の予約 \((s,e)\) との間隔 \(s - \text{prev_end}\) を計算し、最大値を更新する。
4. 最後に、最後の予約終了から \(T\) までの空き \(T - \text{prev_end}\) でも最大値を更新する。
5. 最大値を出力する。

予約が重ならないので、ソート後は「前の終了」と「次の開始」の差を取るだけで空き時間が確定します（負になることもありません）。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（区間を配列に保持）

実装のポイント

• 端の空き時間（\(0\)〜最初、最後〜\(T\)）を忘れずに計算します。

• 入力が最大 \(2\times 10^5\) なので、Pythonでは sys.stdin.readline を使うと安定します。

• ans = intervals[0][0] として最初の空きを初期値にすると、その後の更新が簡潔になります。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, T = map(int, input().split())
    intervals = [tuple(map(int, input().split())) for _ in range(N)]
    intervals.sort()

    ans = intervals[0][0]  # gap from 0 to first start
    prev_end = intervals[0][1]

    for s, e in intervals[1:]:
        if s - prev_end > ans:
            ans = s - prev_end
        prev_end = e

    if T - prev_end > ans:
        ans = T - prev_end

    print(ans)

if __name__ == "__main__":
    main()

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