253. Meeting Rooms II
mediumAsked at ShopifyShopify reframes this as 'how many fulfillment workers do we need to handle overlapping order windows?' It's the canonical sweep-line + heap or chronological-events problem in Shopify's onsite loop.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Shopify loops.
- Glassdoor (2026-Q1)— Shopify Senior Backend + Production Engineer onsites cite Meeting Rooms II framed as concurrent-task scheduling.
- Blind (2025-12)— Shopify L4+ offers reference this with the heap follow-up.
Problem
Given an array of meeting time intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required.
Constraints
1 <= intervals.length <= 10^40 <= start_i < end_i <= 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 count
For each interval, count how many others overlap it; max across all intervals is the answer.
- Time
- O(n^2)
- Space
- O(1)
function minMeetingRoomsBrute(intervals) {
let best = 0;
for (let i = 0; i < intervals.length; i++) {
let count = 0;
for (let j = 0; j < intervals.length; j++) {
const [a, b] = intervals[i];
const [c, d] = intervals[j];
if (a < d && c < b) count++;
}
best = Math.max(best, count);
}
return best;
}Tradeoff: O(n^2) and the wrong mental model for the problem. Mention it only as the starting point that motivates sorting + sweep.
2. Sort starts + sort ends, two-pointer sweep
Sort start times and end times independently. Walk starts; whenever a start happens before the next end, you need an extra room. Otherwise advance the end pointer.
- Time
- O(n log n)
- Space
- O(n)
function minMeetingRoomsSweep(intervals) {
const n = intervals.length;
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, endPtr = 0;
for (let i = 0; i < n; i++) {
if (starts[i] < ends[endPtr]) rooms++;
else endPtr++;
}
return rooms;
}Tradeoff: Elegant and short. Two independent sorts, then a single sweep. Same O(n log n) as the heap version but no heap dependency. Many Shopify interviewers prefer this for its clarity.
3. Min-heap of end times (canonical)
Sort by start time. Maintain a min-heap of end times for currently-ongoing meetings. For each new meeting: if it starts >= heap top, pop (room freed); push the new end. Heap size = rooms needed.
- Time
- O(n log n)
- Space
- O(n)
class MinHeap {
constructor() { this.h = []; }
size() { return this.h.length; }
peek() { return this.h[0]; }
push(v) { this.h.push(v); this._up(this.h.length - 1); }
pop() {
const top = this.h[0];
const last = this.h.pop();
if (this.h.length) { this.h[0] = last; this._down(0); }
return top;
}
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.h[p] > this.h[i]) {
[this.h[p], this.h[i]] = [this.h[i], this.h[p]];
i = p;
} else break;
}
}
_down(i) {
const n = this.h.length;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let smallest = i;
if (l < n && this.h[l] < this.h[smallest]) smallest = l;
if (r < n && this.h[r] < this.h[smallest]) smallest = r;
if (smallest === i) break;
[this.h[smallest], this.h[i]] = [this.h[i], this.h[smallest]];
i = smallest;
}
}
}
function minMeetingRooms(intervals) {
if (!intervals.length) return 0;
intervals.sort((a, b) => a[0] - b[0]);
const heap = new MinHeap();
heap.push(intervals[0][1]);
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= heap.peek()) heap.pop();
heap.push(intervals[i][1]);
}
return heap.size();
}Tradeoff: Mirrors the real-world mental model: each room is an end-time on the heap; when a new meeting can reuse a freed room, swap. Senior Shopify candidates are expected to write this version explicitly.
Shopify-specific tips
Shopify's expected dialogue: name BOTH the heap and the sweep approach, then justify whichever you write. The interviewer often asks 'what if the input is a stream' — that pushes you toward the heap (incremental update friendly) and rules out the sweep (needs the full input sorted). Volunteer the streaming variant unprompted.
Common mistakes
- Treating [1,4] and [4,5] as overlapping — by convention here, an end time is NOT inclusive; [4,5] starts at exactly 4 which is when [1,4] ends, so they don't overlap. Confirm with the interviewer.
- Sorting intervals by start in the sweep version (the sweep uses two separate sorted arrays of starts and ends, NOT sorted pairs).
- Forgetting to handle the empty input case.
- Off-by-one in heap.peek() comparison — use >= not > for the room-reuse case (touching is fine).
Follow-up questions
An interviewer at Shopify may pivot to one of these next:
- Return the actual room assignments per meeting.
- Variable room capacities — multiple meetings can share a large room.
- Streaming version — meetings arrive in chronological order.
- What if meetings can be moved by up to T minutes to reduce room count?
- LeetCode 252 — Meeting Rooms I (can ONE room handle everything?).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Heap vs sweep — which is canonical?
Both are O(n log n) and Shopify accepts either. The heap mirrors the real-world simulation (rooms with end times) and generalizes to streaming inputs. The sweep is shorter to write and easier to debug. Mention both; pick the heap if the follow-up is about streaming.
Why does the start-end sort trick work?
Because the answer is the maximum number of meetings simultaneously active at any instant, which equals the largest (starts_seen - ends_seen) prefix difference. Walking sorted starts and ends together gives you that count without explicitly enumerating instants.
Free learning resources
Curated free links for this problem.