Overview

Given a list of meeting start times and end times, the problem is to assign meetings to the minimum number of meeting rooms such that no times overlap.

Analysis

This problem is a variant of the interval scheduling problem, where all intervals (meetings) need to be covered using the minimum number of resources (meeting rooms). The key observation is that the minimum number of meeting rooms required equals the maximum number of meetings occurring simultaneously. In other words, if we count the maximum number of overlapping meetings at any point in time, that gives us the minimum number of meeting rooms.

A naive approach would compute the overlap count for every time point (e.g., at each meeting’s start and end time), resulting in a time complexity of \(O(N^2)\) or \(O(N \times \text{range of times})\), which is too slow given the constraints (\(N \leq 2 \times 10^5\), times up to \(10^9\)).

Algorithm

An efficient solution follows these steps: 1. Sort all meetings by their start time \(S_i\). 2. Use a min-heap (priority queue) to manage the end times of currently occupied meeting rooms. The top of the heap is the earliest ending meeting time. 3. For each meeting, if the current meeting’s start time \(S_i\) is greater than or equal to the top of the heap (the earliest ending meeting time), then that room can be reused. In that case, remove that end time from the heap and add the new end time \(E_i\). 4. Otherwise, a new meeting room is needed, so add the new end time \(E_i\) to the heap. 5. The final size of the heap is the minimum number of meeting rooms required.

This method greedily reuses meeting rooms and schedules all meetings with the minimum number of rooms.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting takes \(O(N \log N)\), and heap operations (push/pop) for each meeting take \(O(\log N)\), so the total is \(O(N \log N)\).
• Space complexity: \(O(N)\)
  • Because the meeting list and heap can grow up to size \(N\).

Implementation Notes

• Use Python’s heapq module to implement the min-heap. We take advantage of the fact that the top of the heap is the minimum value.

• Sorting meetings by start time is crucial. This allows us to process meetings in chronological order.

• The heap holds the current end time of each meeting room. When a new meeting starts, we check whether the room that ends earliest can be reused.

  Source Code

import heapq

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    meetings = []
    index = 1
    for i in range(n):
        s = int(data[index])
        e = int(data[index + 1])
        index += 2
        meetings.append((s, e))
    
    meetings.sort(key=lambda x: x[0])
    
    rooms = []
    heapq.heappush(rooms, meetings[0][1])
    
    for i in range(1, n):
        s, e = meetings[i]
        earliest_end = rooms[0]
        if s >= earliest_end:
            heapq.heappop(rooms)
        heapq.heappush(rooms, e)
    
    print(len(rooms))

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.