Skip to main content

253. Meeting Rooms II

mediumAsked at Shopify

Shopify 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 Alex Chen, 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^4
  • 0 <= start_i < end_i <= 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 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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →