Overview

Given a time range from \(0\) to \(T\), this problem asks you to find the length of the longest “free time” slot, excluding the given \(N\) reservation time slots (which do not overlap).

Analysis

Free time occurs in the following three patterns: 1. From time \(0\) to the “start time of the first reservation” 2. From the “end time of a reservation” to the “start time of the next reservation” 3. From the “end time of the last reservation” to time \(T\)

To compute these efficiently, the reservations need to be sorted in ascending order of time (earliest first). Since the input may have reservations in an arbitrary order, the standard approach is to first sort by start time.

Once the reservations are sorted chronologically, we can maintain a variable current_time to track the current time, and by taking the difference with each reservation’s start time, we can sequentially check consecutive free time slots.

Algorithm

1. Store all reservations \((S_i, E_i)\) in a list and sort them in ascending order by start time \(S_i\).
2. Initialize a variable current_time representing “the current time being examined” to \(0\).
3. Initialize a variable max_gap to hold the maximum free time to \(0\).
4. Iterate through the sorted reservations one by one and perform the following:
   • Compute the free time length gap = (reservation start time) - current_time.
   • If gap is greater than max_gap, update it.
   • Update current_time to the “reservation end time”.
5. Finally, compute the free time from when the last reservation ends to time \(T\):
   • Compute final_gap = T - current_time and update max_gap.
6. Output max_gap.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the reservations takes \(O(N \log N)\). The subsequent scan is \(O(N)\), so the overall complexity is dominated by sorting. Since \(N = 2 \times 10^5\), this is well within the time limit.
• Space complexity: \(O(N)\)
  • This is the memory required to store the \(N\) reservation entries in a list.

Implementation Notes

• Importance of sorting: Since the input is not necessarily in chronological order, sorting must always be performed.

• Edge handling: Don’t forget to compute the free time before the first reservation (from time \(0\)) and after the last reservation (up to time \(T\)).

• Fast I/O: Since \(N\) can be large, in Python using sys.stdin.read().split() or similar to read all input at once can reduce execution time.

  Source Code

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()

This editorial was generated by gemini-3-flash-preview.