Skip to main content

21. Meeting Rooms II

mediumAsked at Expedia

Find the minimum number of rooms to hold all meetings — the same min-heap interval logic Expedia uses to determine the minimum hotel inventory needed to cover overlapping check-in/check-out windows.

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

Problem

Given an array of meeting time intervals intervals where intervals[i] = [start, end], return the minimum number of conference rooms required.

Constraints

  • 0 <= 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] needs one room. [5,10] overlaps and needs a second. [15,20] can reuse the room freed at 10.

Example 2

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

Approaches

1. Sort + chronological scan

Separate start and end times into two sorted arrays; use two pointers to count the high-water concurrent meetings.

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, maxRooms = 0;
  let s = 0, e = 0;

  while (s < intervals.length) {
    if (starts[s] < ends[e]) {
      rooms++;
      s++;
    } else {
      rooms--;
      e++;
    }
    maxRooms = Math.max(maxRooms, rooms);
  }
  return maxRooms;
}

Tradeoff:

2. Min-heap on end times

Sort by start; maintain a min-heap of current room end times. If the earliest ending room is free, reuse it; otherwise allocate 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 stores end times of active meetings
  const heap = [intervals[0][1]];

  for (let i = 1; i < intervals.length; i++) {
    heap.sort((a, b) => a - b);
    if (intervals[i][0] >= heap[0]) {
      heap.shift(); // reuse room
    }
    heap.push(intervals[i][1]);
  }
  return heap.length;
}

Tradeoff:

Expedia-specific tips

Expedia hotel-supply teams ask this exact pattern. Walk through the min-heap approach and articulate the real-world analogy: each heap entry is a room whose last checkout time we track. They reward candidates who instantly map the algorithm to inventory management without prompting.

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

Practice these live with InterviewChamp.AI →