Skip to main content

24. Meeting Rooms II

mediumAsked at Lyft

Find the minimum number of rooms for overlapping meetings — Lyft maps this to how many concurrent driver-pickup windows they need to keep open at a hub so no ride request is ever left unserviced.

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

Problem

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

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

Explanation: Meeting [0,30] runs the whole time. [5,10] and [15,20] each need a room, but [15,20] can reuse [5,10]'s room after it ends. So 2 rooms suffice.

Example 2

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

Approaches

1. Two sorted arrays (chronological sweep)

Separate start and end times into two sorted arrays. Walk through starts; if the earliest end has passed, reuse that room. Count the peak concurrent rooms.

Time
O(n log n)
Space
O(n)
function minMeetingRooms(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, endPtr = 0;
  for (let i = 0; i < starts.length; i++) {
    if (starts[i] < ends[endPtr]) {
      rooms++;
    } else {
      endPtr++;
    }
  }
  return rooms;
}

Tradeoff:

2. Min-heap of end times

Sort by start time. Maintain a min-heap of end times for active meetings. For each meeting, if heap top <= current start, pop (reuse room). Push current end. Heap size = rooms needed.

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

  // Simulate min-heap with sorted array for interview clarity
  const heap = [];
  for (const [start, end] of intervals) {
    if (heap.length && heap[0] <= start) {
      heap.shift();
    }
    heap.push(end);
    heap.sort((a, b) => a - b);
  }
  return heap.length;
}

Tradeoff:

Lyft-specific tips

Lyft loves interval problems because ride scheduling is all about overlapping time windows. Walk the interviewer through a concrete rideshare example: 'Each interval is a driver's committed ride window; we need to know how many simultaneous drivers to have on call.' The two-pointer approach is clean and O(n log n) — but if the interviewer pushes for a heap, know that it models freeing a room at the earliest possible moment.

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 Lyft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →