Skip to main content

253. Meeting Rooms II

mediumAsked at Google

Given meeting intervals, return the minimum number of rooms required. Google asks this to test whether you reach for a min-heap of end times or the sweep-line / two-pointer counter, and can articulate the start/end event framing.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4 onsite reports cite this as the intervals round.
  • Blind (2025-12)— Recurring Google interview problem.

Problem

Given an array of meeting time intervals where intervals[i] = [start, end], return the minimum number of conference rooms required.

Constraints

  • 1 <= intervals.length <= 10^4
  • 0 <= start < end <= 10^6

Examples

Example 1

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

Example 2

Input
intervals = [[7,10],[2,4]]
Output
1

Approaches

1. Brute-force pair-overlap matrix

Build an n x n matrix of which meetings overlap, then find the max clique.

Time
O(n^2) or worse
Space
O(n^2)
// Brute-force outline only — building the overlap matrix is O(n^2)
// and finding max clique is NP-hard in general. Mention only.

Tradeoff: Wrong framing. Acknowledge the mistake and move to the sweep-line.

2. Sort + min-heap of end times (optimal)

Sort by start. For each meeting, if its start >= the earliest end in the heap, reuse that room (pop); else, allocate new (push). Heap size is the answer.

Time
O(n log n)
Space
O(n)
// MinHeap helper (numbers)
class MinHeap {
  constructor() { this.data = []; }
  push(v) {
    this.data.push(v);
    let i = this.data.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[p] <= this.data[i]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  pop() {
    if (!this.data.length) return undefined;
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) {
      this.data[0] = last;
      let i = 0;
      while (true) {
        let l = 2*i+1, r = 2*i+2, best = i;
        if (l < this.data.length && this.data[l] < this.data[best]) best = l;
        if (r < this.data.length && this.data[r] < this.data[best]) best = r;
        if (best === i) break;
        [this.data[best], this.data[i]] = [this.data[i], this.data[best]];
        i = best;
      }
    }
    return top;
  }
  peek() { return this.data[0]; }
}

function minMeetingRooms(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const heap = new MinHeap();
  for (const [start, end] of intervals) {
    if (heap.data.length && heap.peek() <= start) heap.pop();
    heap.push(end);
  }
  return heap.data.length;
}

Tradeoff: Heap tracks the earliest-finishing room. When the next meeting starts after the earliest end, we reuse that room. Clean, O(n log n).

3. Sweep line / two-pointer (alternative optimal)

Separate starts and ends, sort each. Sweep with two pointers; on each start that precedes the next end, increment count.

Time
O(n log n)
Space
O(n)
function minMeetingRoomsSweep(intervals) {
  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 rooms = 0, max = 0, e = 0;
  for (let s = 0; s < starts.length; s++) {
    if (starts[s] < ends[e]) rooms++;
    else e++;
    max = Math.max(max, rooms);
  }
  return max;
}

Tradeoff: Same complexity but no heap. Often the cleanest whiteboard solution because the start/end event abstraction is concise.

Google-specific tips

Google interviewers value the start/end event framing. Articulate: 'Each meeting contributes one +1 at its start and one -1 at its end. The answer is the max running sum.' Whether you implement with a heap or sweep line, that framing is what the interviewer wants to hear before any code.

Common mistakes

  • Using start AT end as conflicting (it's not — meeting ends exactly when next starts is fine).
  • Sorting by end instead of start — works but the heap loses its 'earliest end' meaning.
  • Treating intervals as ranges and counting overlaps via O(n^2) double-loop.

Follow-up questions

An interviewer at Google may pivot to one of these next:

  • Return the actual room assignments per meeting.
  • What if rooms had capacity?
  • What if meetings could be split across rooms?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Heap or sweep line — which is preferred?

Both score equally. Sweep line is usually faster to code without bugs. The heap version generalizes more cleanly to weighted variants.

Why is [start, end) the right convention?

If meeting A ends at 10 and meeting B starts at 10, they don't conflict. Treating end as exclusive (the convention) lets you reuse the room without overlap.

Practice these live with InterviewChamp.AI

Drill Meeting Rooms II and other Google interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →