Overview

This is a problem of finding the maximum number of meetings occurring simultaneously (= the minimum number of meeting rooms required), when each meeting’s time interval must not overlap with others in the same room.

Analysis

Meetings that cannot be placed in the same room are those whose “times overlap,” so the minimum number of meeting rooms equals the maximum value of “the number of meetings being held simultaneously at any given time.” Intuitively, if there is a moment when \(k\) meetings are running simultaneously, at least \(k\) rooms are needed. Conversely, if the number of simultaneous meetings is always at most \(k\), then \(k\) rooms are sufficient to assign them in order.

A naive approach of “examining each meeting in order and searching for an available room” with linear search over the room list would result in \(O(N^2)\) in the worst case, which is too slow for \(N \le 2\times 10^5\).

Instead, we use the idea of listing “start times” and “end times” separately, and sweeping along the time axis: - When a meeting starts, increment the simultaneous count by \(+1\) - When a meeting ends, decrement the simultaneous count by \(-1\)

Then we take the maximum of this count.

An important note: since the intervals are half-open \([S_i, E_i)\), meetings do not overlap if the end time and start time are the same. In other words, when \(S = E\) occurs at the same time, we need to “process the end first.” In the code, this is achieved by using the condition starts[i] < ends[j], so that when they are equal, the end event (else branch) is processed first.

Example: \((S,E)=(1,3),(3,5)\) can share the same room. Start array: \([1,3]\), End array: \([3,5]\) At time 3, starts[i] < ends[j] does not hold, so the end is processed first, preventing the simultaneous count from increasing.

Algorithm

1. Create the start time array starts and end time array ends for all meetings.
2. Sort starts and ends each in ascending order.
3. Prepare two pointers i (for starts) and j (for ends), and maintain cur, the number of currently ongoing meetings.
4. While i < N, compare the next occurring event:
   • If starts[i] < ends[j], the next event is a “start,” so cur += 1, i += 1
   • Otherwise (starts[i] >= ends[j]), the next event is an “end” (end takes priority at the same time), so cur -= 1, j += 1
5. Update the answer ans with the maximum value of cur encountered during the process, and output ans at the end.

This is a classic example of “sorting events on the time axis and sweeping (sweep line).”

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting the starts and ends)
• Space complexity: \(O(N)\) (for the start and end arrays)

Implementation Notes

• Since the intervals are half-open \([S,E)\), when \(S == E\), they must be treated as non-overlapping. The comparison starts[i] < ends[j] ensures that when they are equal, the end is processed first.

• Since the input can be as large as \(2\times 10^5\), reading all input at once with sys.stdin.buffer.read() is faster.

• The sweep loop only needs to run “until all starts are processed” (once we process all \(N\) starts, the maximum simultaneous count is determined).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    starts = [0] * n
    ends = [0] * n
    idx = 1
    for i in range(n):
        starts[i] = data[idx]
        ends[i] = data[idx + 1]
        idx += 2

    starts.sort()
    ends.sort()

    i = j = 0
    cur = ans = 0
    while i < n:
        if starts[i] < ends[j]:
            cur += 1
            if cur > ans:
                ans = cur
            i += 1
        else:
            cur -= 1
            j += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.