概要

\(0\) から \(T\) までの時間の中で、与えられた \(N\) 個の予約時間帯（重なりなし）を除いた「空き時間」のうち、最も長いものの長さを求める問題です。

考察

空き時間が発生するのは、以下の3つのパターンです。 1. 時刻 \(0\) から「最初の予約の開始時刻」まで 2. 「ある予約の終了時刻」から「次の予約の開始時刻」まで 3. 「最後の予約の終了時刻」から時刻 \(T\) まで

これらを効率よく計算するためには、予約が時刻の昇順（早い順）に並んでいる必要があります。入力では予約の順番がバラバラである可能性があるため、まずは開始時刻でソートを行うのが定石です。

予約が時間順に並んでいれば、現在の時刻を管理する変数 current_time を用意し、各予約の開始時刻との差を取ることで、連続した空き時間を順番にチェックしていくことができます。

アルゴリズム

1. すべての予約 \((S_i, E_i)\) をリストに格納し、開始時刻 \(S_i\) で昇順にソートします。
2. 「現在見ている時刻」を表す変数 current_time を \(0\) で初期化します。
3. 最大空き時間を保持する変数 max_gap を \(0\) で初期化します。
4. ソート済みの予約を一つずつ取り出し、以下の処理を行います：
   • 空き時間の長さ gap = (予約の開始時刻) - current_time を計算する。
   • gap が max_gap より大きければ更新する。
   • current_time を「予約の終了時刻」に更新する。
5. 最後に、最後の予約が終わってから時刻 \(T\) までの空き時間を計算します：
   • final_gap = T - current_time を計算し、max_gap を更新する。
6. max_gap を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 予約のソートに \(O(N \log N)\) かかります。その後の走査は \(O(N)\) なので、全体の計算量はソートが支配的になります。\(N = 2 \times 10^5\) なので、制限時間内に十分間に合います。
• 空間計算量: \(O(N)\)
  • \(N\) 個の予約情報をリストに保存するために必要なメモリ量です。

実装のポイント

• ソートの重要性: 入力が時刻順とは限らないため、必ずソートを行います。

• 端の処理: 最初の予約の前（時刻 \(0\) から）と、最後の予約の後（時刻 \(T\) まで）の計算を忘れないようにします。

• 高速な入出力: \(N\) が大きいため、Python の場合は sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 予約の件数, T: 終了時刻
    N = int(input_data[0])
    T = int(input_data[1])
    
    # 予約情報をリストに格納
    reservations = []
    for i in range(N):
        s = int(input_data[2 + 2*i])
        e = int(input_data[3 + 2*i])
        reservations.append((s, e))
    
    # 開始時刻でソート
    reservations.sort()
    
    max_gap = 0
    current_time = 0
    
    # 各予約の間の空き時間を計算
    for s, e in reservations:
        gap = s - current_time
        if gap > max_gap:
            max_gap = gap
        current_time = e
    
    # 最後の予約から時刻 T までの空き時間を計算
    final_gap = T - current_time
    if final_gap > max_gap:
        max_gap = final_gap
        
    # 結果を出力
    print(max_gap)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。