Overview

Given booking information for a meeting room, find the longest continuous free time.

Analysis

In this problem, multiple time slots (bookings) for a meeting room are given, and we need to find the longest free time that exists “between” or “before/after” these bookings.

The key observations are as follows: - Since bookings are guaranteed not to overlap, we can simply sort them by start time and process them in order. - Free time falls into the following 3 patterns: 1. Time before the first booking starts (from time \(0\) to the first \(S_i\)) 2. Time between the end of one booking and the start of the next booking (\(E_i\) to \(S_{i+1}\)) 3. Time after the last booking ends (from the last \(E_i\) to time \(T\))

By examining these free times in order and taking the maximum, we can obtain the answer.

A naive approach of simulating all time units (0 to T) is infeasible. This is because \(T\) can be up to \(10^9\), and checking one second at a time would result in TLE (Time Limit Exceeded).

In this problem, the number of bookings \(N\) is at most \(2 \times 10^5\), so the approach of sorting bookings and checking the gaps between them is practical.

Algorithm

1. Read the input and sort the bookings by start time \(S_i\).
2. Calculate the free time before the first booking:
   $\(\text{max\_gap} = \max(\text{max\_gap}, S_1 - 0)\)$
3. Calculate the free time between each pair of adjacent bookings:
   $\(\text{gap} = S_{i+1} - E_i\)\( \)\(\text{max\_gap} = \max(\text{max\_gap}, \text{gap})\)$
4. Calculate the free time after the last booking:
   $\(\text{gap} = T - E_N\)\( \)\(\text{max\_gap} = \max(\text{max\_gap}, \text{gap})\)$
5. Output the maximum \(\text{max\_gap}\).

Concrete Example

Input:

3 20
5 9
12 15
0 3

After sorting bookings by start time:

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

Free times are: - Before time 0–3: none (start time is 0) - Between 3 and 5: length 2 - Between 9 and 12: length 3 - Between 15 and 20: length 5

Therefore, the longest free time is 5.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (storing booking information)

Implementation Notes

• Since the input can be large, sys.stdin.read is used for faster input

• If there are no bookings (\(N=0\)), the meeting room is free all day, so simply output \(T\)

• After sorting, make sure to check all three types of free time without omission: before the first booking, after the last booking, and between consecutive bookings

  Source Code

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

---

This editorial was generated by qwen3-coder-480b.