Overview

Given the schedules of \(N\) meetings, this problem asks us to find the maximum number of meetings occurring simultaneously and calculate the minimum number of meeting rooms required.

Analysis

This problem can be rephrased as: “What is the maximum number of meetings in progress at the same time?” This is because the number of meetings happening simultaneously at any given time equals the number of meeting rooms needed at that time.

A naive approach would be to prepare an array and count the number of meetings at each time point (e.g., using the imos method). However, in this problem, the maximum time value is \(10^9\), which is extremely large. Preparing an array of length \(10^9\) and checking each time point would exceed the memory limit (MLE) or time limit (TLE).

To solve this, we focus only on “the moment a meeting starts” and “the moment a meeting ends.” This is because the meeting situation only changes at these specific times. This technique of extracting only the moments when changes occur (events) and processing them in chronological order is called event sorting.

Algorithm

1. Creating Events: For each meeting \(i\), create the following two events:

   • An event at time \(S_i\) where a meeting starts (the number of rooms in use increases by \(+1\))
   • An event at time \(E_i\) where a meeting ends (the number of rooms in use decreases by \(-1\)) Add these to a list as pairs of (time, delta).

2. Sorting Events: Sort all created events in ascending order of time. What’s important here is the processing order when a “start” and “end” occur at the same time. The problem statement says that if the end time of one meeting coincides with the start time of another meeting, they can be held consecutively in the same meeting room. This means that at the same time, “end (\(-1\))” must be processed before “start (\(+1\))”; otherwise, we would incorrectly determine that an extra meeting room is temporarily needed. Since we represent pairs as (time, delta), when times are equal, the delta value of -1 naturally sorts before 1, satisfying this condition.

3. Computing the Maximum: Process the sorted events in order, computing the current number of rooms in use (the cumulative sum of delta values). The maximum value of the room count recorded during this process is the minimum number of meeting rooms required.

Complexity

• Time complexity: \(O(N \log N)\)
  • There are \(2N\) events, and sorting them takes \(O(N \log N)\) time. The scan after sorting completes in \(O(N)\), so the overall time complexity is \(O(N \log N)\). This is sufficiently fast for the constraint \(N = 2 \times 10^5\).
• Space complexity: \(O(N)\)
  • Since we store \(2N\) events in an array (list), we use \(O(N)\) memory.

Implementation Notes

When sorting events, Python’s sort() method compares by the first element of the tuple (time), and if they are equal, by the second element (delta). By storing end events as (E, -1) and start events as (S, 1) in the list, the events are automatically sorted in the correct order of “end before start at the same time” without needing to write a custom comparison function. This is the elegant and simple beauty of this implementation.

Source Code

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    events = []
    
    idx = 1
    for _ in range(N):
        S = int(data[idx])
        E = int(data[idx+1])
        idx += 2
        events.append((S, 1))
        events.append((E, -1))
        
    events.sort(key=lambda x: (x[0], x[1]))
    
    ans = 0
    current = 0
    for _, val in events:
        current += val
        if current > ans:
            ans = current
            
    print(ans)

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3.1-pro-thinking.