253. Meeting Rooms II
mediumAsked at GoogleGiven 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 Sam K., 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^40 <= start < end <= 10^6
Examples
Example 1
intervals = [[0,30],[5,10],[15,20]]2Example 2
intervals = [[7,10],[2,4]]1Approaches
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.
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.