Overview

Given \(N\) time intervals, this is the so-called “Interval Partitioning” problem: find the minimum number of meeting rooms needed to assign all meetings such that no two meetings in the same room overlap in time.

Analysis

Key Insight: The maximum number of simultaneous meetings is the answer

If \(k\) meetings are happening simultaneously at some moment, then at least \(k\) rooms are needed just for that moment. Conversely, it is known that using a greedy approach, all meetings can be assigned using exactly “the maximum number of simultaneous meetings” rooms.

Problem with the naive approach

Checking overlap for all pairs of meetings \((i, j)\) takes \(O(N^2)\), which will result in TLE for \(N \leq 2 \times 10^5\).

Solution: Greedy + Min-Heap

Sort the meetings in ascending order of start time and process them sequentially. When assigning each meeting, if “the room that becomes available earliest among all currently used rooms” finishes before or at the start time of the new meeting, that room can be reused. To efficiently determine this, we use a min-heap (priority queue).

Concrete Example

Suppose there are 3 meetings: \([1,4), [2,5), [4,7)\).

1. Meeting \([1,4)\): The heap is empty, so use a new room → Heap: \(\{4\}\)
2. Meeting \([2,5)\): The heap’s minimum value \(4 > 2\), so reuse is not possible, use a new room → Heap: \(\{4, 5\}\)
3. Meeting \([4,7)\): The heap’s minimum value \(4 \leq 4\), so reuse is possible, remove \(4\) and add \(7\) → Heap: \(\{5, 7\}\)

The final heap size is \(2\) → the answer is 2.

Algorithm

1. Sort the \(N\) meetings in ascending order of start time \(S_i\) (breaking ties by ascending end time \(E_i\)).
2. Prepare a min-heap to manage the end times of each meeting room.
3. Process meetings \((S_i, E_i)\) in sorted order:
   • If the heap is not empty and the heap’s minimum value (earliest end time) is \(\leq S_i\), reuse that room (pop the minimum from the heap).
   • Push \(E_i\) onto the heap (in the reuse case this updates the room’s end time; in the new room case this adds a room).
4. The final size of the heap is the minimum number of meeting rooms needed.

Complexity

• Time complexity: \(O(N \log N)\) (\(O(N \log N)\) for sorting, and \(O(\log N)\) heap operations per meeting)
• Space complexity: \(O(N)\) (the heap contains at most \(N\) elements)

Implementation Notes

• Since intervals are half-open \([S_i, E_i)\), when a meeting’s end time equals another meeting’s start time (\(E_j = S_i\)), they do not overlap. The condition heap[0] <= s in the code correctly handles this (using <= rather than <).

• Python’s heapq module provides a min-heap, so “the room that finishes earliest” can be retrieved in \(O(\log N)\).

• When sorting using tuples \((S_i, E_i)\), Python compares by the first element then the second element, so meetings are naturally sorted by start time, with ties broken by end time.

  Source Code

import heapq

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    meetings = []
    for _ in range(N):
        s, e = map(int, input().split())
        meetings.append((s, e))
    
    # Sort by start time, then by end time
    meetings.sort()
    
    # Min-heap of end times of currently used rooms
    heap = []
    
    for s, e in meetings:
        if heap and heap[0] <= s:
            heapq.heappop(heap)
        heapq.heappush(heap, e)
    
    print(len(heap))

main()

---

This editorial was generated by claude4.6opus-thinking.