Overview

This problem asks you to find the longest continuous free time when \(N\) reservations have been made within the available meeting room time from \(0\) to \(T\).

Analysis

Key Insight

The gaps between reservations become “free time”. Free time can be classified into the following 3 types:

1. From time \(0\) until the first reservation starts
2. From when one reservation ends until the next reservation starts (gaps between reservations)
3. From when the last reservation ends until time \(T\)

Concrete Example

For example, suppose \(T = 20\) and there are 3 reservations: \((2, 5), (10, 15), (7, 9)\).

After sorting by start time, we get \((2, 5), (7, 9), (10, 15)\).

Time: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
     [free][reservation1][free][reservation2][reservation3][free time        ]

The free times are: - Time \(0\) to \(2\): length \(2\) - Time \(5\) to \(7\): length \(2\) - Time \(9\) to \(10\): length \(1\) - Time \(15\) to \(20\): length \(5\) ← Longest!

Why Sorting is Necessary

Reservations are not necessarily given in input order. To examine free time chronologically, we need to sort by start time.

Algorithm

1. Read input and store all reservations in an array
2. Sort by start time
3. Calculate the 3 types of free time in order and update the maximum
   • First free time: reservations[0][0] - 0 (start time of the first reservation)
   • Free time between reservations: reservations[i][0] - reservations[i-1][1] (start time of \(i\)-th reservation - end time of \((i-1)\)-th reservation)
   • Last free time: T - reservations[-1][1] (\(T\) - end time of the last reservation)
4. Output the maximum

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting takes \(O(N \log N)\)
  • Calculating free time takes \(O(N)\)
• Space complexity: \(O(N)\)
  • Array to store reservations takes \(O(N)\)

Implementation Notes

1. Don’t forget to sort: Since input is not necessarily in chronological order, make sure to sort by start time.

2. Don’t forget edge cases: In addition to free time between reservations, you must also check free time “before the first reservation” and “after the last reservation”.

3. Tuple sorting: In Python, when you sort tuples of (start_time, end_time), they are automatically sorted by start time (first element takes priority).

4. Be careful with indices: reservations[i][0] represents the start time of the \(i\)-th reservation, and reservations[i][1] represents the end time.

Source Code

def solve():
    N, T = map(int, input().split())
    
    reservations = []
    for _ in range(N):
        s, e = map(int, input().split())
        reservations.append((s, e))
    
    # Sort by start time
    reservations.sort()
    
    max_free_time = 0
    
    # Free time before the first reservation starts
    max_free_time = max(max_free_time, reservations[0][0])
    
    # Free time between reservations
    for i in range(1, N):
        free_time = reservations[i][0] - reservations[i-1][1]
        max_free_time = max(max_free_time, free_time)
    
    # Free time after the last reservation ends
    max_free_time = max(max_free_time, T - reservations[-1][1])
    
    print(max_free_time)

solve()

---

This editorial was generated by claude4.5opus.