AlgoMaster Logo

Meeting Rooms II

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to figure out the maximum number of meetings that overlap at any point in time. That peak overlap count equals the minimum number of rooms required, because at that moment, every one of those overlapping meetings needs its own room.

A hotel makes the idea concrete. Guests check in and check out at different times, and the number of rooms you need depends on the busiest moment, when the most guests are checked in at once. Two guests whose stays overlap cannot share a room.

A meeting room becomes free the moment a meeting ends. If a new meeting starts at or after the end time of an existing meeting, it can reuse that room. So the task reduces to tracking which rooms are free and when.

Key Constraints:

  • 1 <= intervals.length <= 10^4 → With n up to 10,000, an O(n^2) brute force runs up to 100 million operations, which is borderline. O(n log n) is comfortable, so that is the target.
  • 0 <= start_i < end_i <= 10^6 → A meeting always has positive duration since start_i < end_i, so a meeting never overlaps with itself. Time values reach one million, which rules out indexing an array by timestamp unless that array is bounded carefully. The event-based approaches below avoid the timestamp range entirely.

Approach 1: Brute Force (Check All Time Points)

Intuition

The peak number of concurrent meetings always occurs at some meeting's start time. A new overlap can only begin when a meeting starts, so checking the overlap count at every start time captures the maximum. For each meeting, count how many meetings are active at the instant it starts. The largest count over all meetings is the answer.

A meeting j is active at time t when intervals[j][0] <= t and intervals[j][1] > t. The end is strict because a meeting that ends exactly at t has already freed its room.

Algorithm

  1. Initialize maxRooms = 0.
  2. For each meeting i, count how many meetings are active at time intervals[i][0] (the start of meeting i).
  3. A meeting j is active at time t if intervals[j][0] <= t and intervals[j][1] > t.
  4. Update maxRooms with the maximum count found.
  5. Return maxRooms.

Visualization and Code

Loading animation...

Recounting overlaps from scratch for each meeting wastes work. Processing meetings in chronological order lets us maintain the room count incrementally instead.

Approach 2: Sorting + Min-Heap

Intuition

Sorting meetings by start time and processing them one by one simulates room allocation in real time. Maintain a min-heap that stores the end times of all ongoing meetings. The heap's minimum is the time the next room becomes free.

When a new meeting arrives, compare its start time against the heap's minimum. If the earliest-ending meeting finishes before or exactly when the new meeting starts, pop it: that room is reused. Otherwise the new meeting needs a fresh room. In both cases, push the new meeting's end time onto the heap.

The heap size always equals the number of rooms in use, and since the algorithm never shrinks the heap below the current concurrency, the maximum heap size reached is the answer. With the loop as written, every meeting pushes exactly once and pops at most once, so the final heap size is the peak concurrency.

Algorithm

  1. Sort intervals by start time.
  2. Initialize a min-heap. Add the end time of the first meeting.
  3. For each subsequent meeting:
    • If the meeting's start time is >= the smallest end time in the heap, pop the heap (a room is freed).
    • Push the current meeting's end time onto the heap.
  4. Return the size of the heap (it represents the number of rooms needed).

Visualization and Code

Loading animation...

The heap tracks which room frees up, but the answer only depends on how many rooms are free at each moment, not which one. Dropping that bookkeeping leads to a heap-free solution that tracks start and end events separately.

Approach 3: Chronological Ordering (Two Sorted Arrays)

Intuition

Each meeting splits into two events: a start (a room is needed) and an end (a room is freed). Laid out in chronological order, these events let us walk through time and track the room count.

Separate all start times into one array and all end times into another, then sort both. Two pointers sweep through them. Each start that occurs before the next end forces another room. Each time a start meets an end that has already passed, a room is reused. No heap is required, only two sorted arrays and two pointers.

Algorithm

  1. Extract all start times into an array and sort it.
  2. Extract all end times into an array and sort it.
  3. Initialize two pointers startPtr = 0 and endPtr = 0, and a counter rooms = 0.
  4. While startPtr < n:
    • If starts[startPtr] < ends[endPtr], we need a new room (increment rooms). Otherwise, we reuse a room (increment endPtr). Always increment startPtr.
  5. Return rooms.

Visualization and Code

Loading animation...