medium

Meeting Rooms II

Sort meetings by start time and track room end times in a min-heap to count the rooms actually needed.

1. Define the problem

Meeting Rooms II

You are given a list of meetings, where each meeting is written as [start, end]. Return the smallest number of rooms needed so that every meeting can happen. A meeting that ends at time 10 and one that starts at time 10 can share a room, because the first one is already over. Sort the meetings by start time, then keep a min-heap of the end times of the rooms in use . Before each meeting starts, look at the room that frees up soonest: if it is already free, reuse it, otherwise open a new room. The size of the heap at the end is the number of rooms you needed.

Constraints

  • 0 ≤ intervals.length ≤ 104
  • 0 ≤ start < end ≤ 106
  • Meetings may overlap in any way

Example

Inputintervals = [[0, 30], [5, 10], [15, 20]]
Output2

Explanation The meeting from 0 to 30 holds one room the whole time. The meeting from 5 to 10 overlaps it, so a second room opens. The meeting from 15 to 20 can reuse that second room, because the 5 to 10 meeting has finished. Two rooms are enough.

2. Know the words first

In plain terms

Heap
A container that always knows its best item, where best means smallest or largest depending on how you set it up. Adding an item or taking the best item out costs about log n steps, and you never have to sort the whole collection.
Backing array
A heap is stored as one plain list. The item at position i keeps its parent at position (i - 1) / 2 rounded down, and its two children at positions 2i + 1 and 2i + 2. That is why every picture below is a row of numbered boxes.
Min-heap
A heap whose best item is the smallest one. Here that is the room that becomes free at the earliest time.
Peek
Looking at the top item of a heap without removing it. Peeking costs one step.
Why sort first
Handling meetings in start order means that when you look at a meeting, every room in the heap belongs to a meeting that has already begun. Without sorting, the heap would not tell you anything useful.
3. Visualize the solution

The row of boxes is the backing array of the min-heap of room end times, one box per room in use

The row of boxes is the backing array of the min-heap of room end times, one box per room in use
Statussort

Sort by start time. No rooms are open yet, so the heap is empty.

What happens in this step

intervals = [[0, 30], [5, 10], [15, 20]]
sorted by start = [[0, 30], [5, 10], [15, 20]]
heap is empty

This input was already in start order, but sorting still matters in general.
Step 1 of 5

Steps to visualize

  1. Each box is one slot of the list that stores the heap. Slot 0 holds the earliest end time, which is the room that frees up soonest.
  2. A slot showing — means that many rooms have not been needed yet.
  3. For each meeting in start order: if slot 0 is an end time at or before this start, pop it, because that room is free again.
  4. Then always push this meeting end time, which is the room it will occupy.
  5. The number of filled slots at the end is the answer.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row of boxes is the backing array of the min-heap of room end times, one box per room in use
Statussort

Sort by start time. No rooms are open yet, so the heap is empty.

What happens in this step

intervals = [[0, 30], [5, 10], [15, 20]]
sorted by start = [[0, 30], [5, 10], [15, 20]]
heap is empty

This input was already in start order, but sorting still matters in general.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function minMeetingRooms(intervals) {
  if (intervals.length === 0) return 0;

  const sorted = intervals.slice().sort((a, b) => a[0] - b[0]);
  const endTimes = new Heap((a, b) => a - b);

  for (const meeting of sorted) {
    if (endTimes.size() > 0 && endTimes.peek() <= meeting[0]) {
      endTimes.pop();
    }
    endTimes.push(meeting[1]);
  }

  return endTimes.size();
}

class Heap {
  constructor(compare) {
    this.items = [];
    this.compare = compare;
  }

  size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(value) {
    this.items.push(value);
    let child = this.items.length - 1;

    while (child > 0) {
      const parent = (child - 1) >> 1;
      if (this.compare(this.items[child], this.items[parent]) >= 0) break;
      const swap = this.items[child];
      this.items[child] = this.items[parent];
      this.items[parent] = swap;
      child = parent;
    }
  }

  pop() {
    const top = this.items[0];
    const last = this.items.pop();

    if (this.items.length > 0) {
      this.items[0] = last;
      let parent = 0;

      while (true) {
        const left = parent * 2 + 1;
        const right = parent * 2 + 2;
        let best = parent;

        if (left < this.items.length && this.compare(this.items[left], this.items[best]) < 0) best = left;
        if (right < this.items.length && this.compare(this.items[right], this.items[best]) < 0) best = right;
        if (best === parent) break;

        const swap = this.items[parent];
        this.items[parent] = this.items[best];
        this.items[best] = swap;
        parent = best;
      }
    }

    return top;
  }
}
Time
O(n log n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
intervals = [[0, 30], [5, 10], [15, 20]]2example from the docstring
intervals = [[7, 10], [2, 4]]1meetings given out of order that do not overlap
intervals = []0empty input
intervals = [[1, 5]]1smallest non-empty input
intervals = [[1, 5], [5, 9], [9, 12]]1one meeting ends exactly when the next begins, so one room is enough
intervals = [[1, 10], [2, 7], [3, 19], [8, 12], [10, 20], [11, 30]]4larger input where four meetings run at the same time

Keep reading