Frontend Beauty
ESC

Type to search the knowledge base.

Meeting Rooms II

Minimum rooms for all meetings — sort starts and ends, sweep line counting concurrent intervals.

intermediate3 min read
  • dsa
  • intervals
  • interview
  • Google
  • Meta
  • Amazon

The problem

Given meeting intervals [start, end], return the minimum number of conference rooms required.

Input:  [[0,30],[5,10],[15,20]]
Output: 2

Input:  [[7,10],[2,4]]
Output: 1

A room frees at end and can host a meeting starting at the same time (usually).

Brute force

For each meeting, scan how many others overlap it; take max. Correct, O(n²).

Optimal: chronological sweep

Separate starts and ends. Sort both. Walk with two pointers:

  • If next start < next end → need a new room (used++)
  • Else a meeting ended → free a room (used--)
  • Track max(used)
function minMeetingRooms(intervals: number[][]): number {
  if (!intervals.length) return 0;

  const starts = intervals.map((i) => i[0]).sort((a, b) => a - b);
  const ends = intervals.map((i) => i[1]).sort((a, b) => a - b);

  let s = 0;
  let e = 0;
  let used = 0;
  let best = 0;

  while (s < starts.length) {
    if (starts[s] < ends[e]) {
      used++;
      best = Math.max(best, used);
      s++;
    } else {
      used--;
      e++;
    }
  }
  return best;
}
Time O(n log n)
Space O(n)

Heap alternative

Sort meetings by start. Min-heap of end times of rooms in use. For each meeting: if earliest end ≤ start, pop (reuse). Push this end. Heap size = rooms used; track max.

// Interview sketch with sorted array as fake min-heap of ends
function minMeetingRoomsHeap(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);
  const ends: number[] = []; // keep sorted ascending

  for (const [start, end] of intervals) {
    if (ends.length && ends[0] <= start) {
      ends.shift(); // free earliest room
    }
    // insert end in order
    let i = 0;
    while (i < ends.length && ends[i] < end) i++;
    ends.splice(i, 0, end);
  }
  return ends.length; // wrong: need max size during process
}

Correct heap version tracks max size as you go:

function minMeetingRoomsHeapCorrect(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);
  const ends: number[] = [];
  let best = 0;

  for (const [start, end] of intervals) {
    if (ends.length && ends[0] <= start) ends.shift();
    let i = 0;
    while (i < ends.length && ends[i] < end) i++;
    ends.splice(i, 0, end);
    best = Math.max(best, ends.length);
  }
  return best;
}

Prefer the two-pointer sweep in interviews — less fiddly than coding a heap in JS.

Edge cases

  • Empty → 0
  • All sequential non-overlapping → 1
  • All overlapping one point in time → n
  • start == end zero-duration meetings
  • Many ending exactly when others start → reuse (starts[s] < ends[e] strict)

Common bugs

  • Sorting intervals only once and counting adjacent (that’s Meeting Rooms I)
  • Using <= wrong so rooms aren’t reused at exact boundaries
  • Returning final used instead of peak

Interview delivery

  1. Peak concurrency problem.
  2. Sort starts & ends; two pointers.
  3. Or min-heap of ends.
  4. O(n log n).
  5. Trace [[0,30],[5,10],[15,20]] → peak 2.

Further reading