Overview

Given a schedule of meetings, this problem asks for the minimum number of meeting rooms required when assigning rooms such that no time slots overlap.

Analysis

This problem is a variation of “interval scheduling.” A naive approach would be to examine each meeting in order and check whether it can be placed in any already-used meeting room. However, since the number of meetings \(N\) can be up to \(2 \times 10^5\), checking all meeting rooms each time would be too slow (TLE).

The key insight is that “it is optimal to assign the next meeting to the room that finishes earliest.” This avoids unnecessarily using new meeting rooms. To implement this strategy efficiently, it is effective to use a priority queue (heap) that manages end times.

Additionally, by processing meetings in order of start time, we can always handle meetings in the order that may affect future meetings.

For example, consider the following input:

3
1 3
2 4
3 5

After sorting by start time, the meetings are processed in order: - Meeting [1, 3): Use a new meeting room → add 3 to the heap - Meeting [2, 4): No room is available yet, so use a new meeting room → add 4 to the heap - Meeting [3, 5): The first meeting has ended, so reuse that room → remove 3 from the heap, add 5

The final size of the heap becomes the answer (the number of meeting rooms used).

Algorithm

1. Sort all meetings by start time \(S_i\).
2. Prepare a priority queue (min-heap) to manage the “latest end time” of each meeting room.
3. Process each meeting as follows:
   • If the minimum value of the heap (the end time of the room that finishes earliest) is before the current meeting’s start time, reuse that room (remove from the heap and add the new end time).
   • Otherwise, use a new meeting room (add the end time to the heap).
4. The final size of the heap is the minimum number of meeting rooms required.

Complexity

• Time complexity: \(O(N \log N)\)
  (\(O(N \log N)\) for sorting, \(O(\log N)\) for heap operations on each element)
• Space complexity: \(O(N)\)
  (The heap holds at most \(N\) elements)

Implementation Notes

• Don’t forget to sort meetings by start time.

• Only end times are stored in the heap.

• heap[0] gives the earliest end time (Python’s heapq implements a min-heap).

• Cases with multiple meetings having the same start and end times are handled correctly.

  Source Code

import heapq

N = int(input())
meetings = [tuple(map(int, input().split())) for _ in range(N)]

# 開始時刻でソート
meetings.sort()

# 終了時刻を管理する優先度付きキュー
heap = []

for s, e in meetings:
    # 一番早く終わる部屋が使えるかどうかチェック
    if heap and heap[0] <= s:
        heapq.heappop(heap)
    # 現在の会議の終了時刻を追加
    heapq.heappush(heap, e)

print(len(heap))

---

This editorial was generated by qwen3-coder-480b.