Overview

Given reservation intervals (time periods in use) for a meeting room, find the length of the longest “continuous free time (interval with no reservations)” within the time range \(0\) to \(T\).

Analysis

The key insight is that “free time only appears in the ‘gaps’ between reservations.” Furthermore, since reservations do not overlap, sorting them by start time reveals that free time consists of only the following 3 types:

1. \([0, S_{\text{first}})\) (before the first reservation)
2. \([E_i, S_{i+1})\) (between two consecutive reservations)
3. \([E_{\text{last}}, T)\) (after the last reservation)

A naive approach of “checking each time unit one by one and counting free slots” is impractical since \(T\) can be up to \(10^9\) (this would be \(O(T)\) and result in TLE). Instead, it suffices to use only the reservation interval information to examine the “gaps between adjacent reservations.”

Concrete example: - \(T=10\) - Reservations are \((2,3),(5,7)\) Free intervals are \([0,2)\) with length 2, \([3,5)\) with length 2, \([7,10)\) with length 3 The maximum is 3.

Algorithm

1. Sort the reservation intervals \((S_i, E_i)\) in ascending order by start time \(S_i\).
2. As an initial candidate for the answer, include the free time before the first reservation: \(S_{\text{first}}-0\).
3. While keeping track of the previous reservation’s end time prev_end, compute the gap \(s - \text{prev\_end}\) to the next reservation \((s,e)\), and update the maximum.
4. Finally, update the maximum with the free time from the last reservation’s end to \(T\): \(T - \text{prev\_end}\).
5. Output the maximum.

Since reservations do not overlap, after sorting, the free time is determined simply by taking the difference between “previous end” and “next start” (this value is never negative).

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (storing intervals in an array)

Implementation Notes

• Don’t forget the free time at the boundaries (\(0\) to the first reservation, and the last reservation to \(T\)).

• Since the input can be up to \(2\times 10^5\), using sys.stdin.readline in Python ensures stability.

• By initializing ans = intervals[0][0] as the first free interval, subsequent updates become concise.

  Source Code

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

This editorial was generated by gpt-5.2-high.