Skip to main content

27. Meeting Rooms II

mediumAsked at Box

Find the minimum number of rooms required for overlapping meetings — Box uses an identical interval-scheduling model to determine peak concurrent file-lock holders and size their distributed lock server fleet.

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 schedule all meetings without conflicts.

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] can reuse the same second room.

Example 2

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

Approaches

1. Brute force — simulation

Sort meetings by start; maintain a list of active end times. For each new meeting, scan for the earliest-ending room that is free; if none, open a new room.

Time
O(n^2)
Space
O(n)
function minMeetingRooms(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const rooms = []; // active end times
  for (const [start, end] of intervals) {
    let assigned = false;
    for (let i = 0; i < rooms.length; i++) {
      if (rooms[i] <= start) {
        rooms[i] = end;
        assigned = true;
        break;
      }
    }
    if (!assigned) rooms.push(end);
  }
  return rooms.length;
}

Tradeoff:

2. Optimal — min-heap of end times

Sort by start time. Use a min-heap of end times; if the earliest-ending room finishes before the next meeting starts, reuse it (pop and push new end); otherwise add a room.

Time
O(n log n)
Space
O(n)
// Min-heap implementation inline
class MinHeap {
  constructor() { this.h = []; }
  push(v) {
    this.h.push(v);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p] <= this.h[i]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      while (true) {
        let s = i, l = 2*i+1, r = 2*i+2;
        if (l < this.h.length && this.h[l] < this.h[s]) s = l;
        if (r < this.h.length && this.h[r] < this.h[s]) s = r;
        if (s === i) break;
        [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
        i = s;
      }
    }
    return top;
  }
  peek() { return this.h[0]; }
  size() { return this.h.length; }
}

function minMeetingRooms(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const heap = new MinHeap();
  for (const [start, end] of intervals) {
    if (heap.size() > 0 && heap.peek() <= start) {
      heap.pop();
    }
    heap.push(end);
  }
  return heap.size();
}

Tradeoff:

Box-specific tips

Box expects you to code the min-heap yourself since JavaScript has no built-in PriorityQueue — walk through the sift-up and sift-down operations clearly. The follow-up they love: 'Could you solve this without a heap using two sorted arrays?' Yes — separate starts and ends, use two pointers; if end[j] <= start[i] a room is freed. Both approaches show interval reasoning that applies directly to Box's file-lock scheduling and real-time collaboration conflict detection.

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

Practice these live with InterviewChamp.AI →