18. Meeting Rooms II

mediumAsked at Instacart

Find the minimum number of rooms required to schedule overlapping meetings — Instacart mirrors this directly onto delivery-window scheduling where overlapping shopper slots compete for the same fulfillment capacity.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

Given an array of meeting time intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required to hold all meetings.

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

Explanation: Meeting [0,30] overlaps with both others, but [5,10] and [15,20] don't overlap with each other, so only 2 rooms are needed.

Example 2

Input

intervals = [[7,10],[2,4]]

Output

Approaches

1. Sort + brute-force room scan

Sort by start time. For each interval, scan all existing rooms to find one that's free.

Time: O(n^2)
Space: O(n)

function minMeetingRooms(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const roomEnd = [];

  for (const [start, end] of intervals) {
    let placed = false;
    for (let i = 0; i < roomEnd.length; i++) {
      if (roomEnd[i] <= start) {
        roomEnd[i] = end;
        placed = true;
        break;
      }
    }
    if (!placed) roomEnd.push(end);
  }
  return roomEnd.length;
}

Tradeoff:

2. Min-heap (priority queue on end times)

Sort by start time. Keep a min-heap of earliest-ending rooms. If the top of the heap ends before the next meeting starts, reuse that room; otherwise add a new room.

Time: O(n log n)
Space: O(n)

function minMeetingRooms(intervals) {
  if (!intervals.length) return 0;
  intervals.sort((a, b) => a[0] - b[0]);

  // Min-heap simulated via sorted array (fine for interview; note real heap is O(log n) per op)
  const heap = [];

  function heapPush(val) {
    heap.push(val);
    heap.sort((a, b) => a - b);
  }
  function heapPop() {
    return heap.shift();
  }

  heapPush(intervals[0][1]);

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    if (heap[0] <= start) {
      heapPop();
    }
    heapPush(end);
  }
  return heap.length;
}

Tradeoff:

Instacart-specific tips

Instacart's scheduling infrastructure assigns shoppers to delivery windows under tight overlap constraints. Interviewers look for the heap insight — reusing the earliest-finishing slot — and whether you can articulate why sorting start times alone is insufficient without tracking ongoing room occupancy.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →