22. Meeting Rooms II

mediumAsked at Square

Find how many Square Appointments booking slots overlap simultaneously — Square's scheduling infrastructure uses this interval-heap pattern to compute the minimum number of POS terminals needed to handle concurrent appointment peaks without double-booking.

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

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

Explanation: Meeting [0,30] overlaps with both others; [5,10] and [15,20] do not overlap each other, so 2 rooms suffice.

Example 2

Input

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

Output

Approaches

1. Sort + min-heap

Sort by start time; use a min-heap of end times. For each meeting, if the earliest ending room finishes before this one starts, reuse it (pop and push new end); otherwise add a room. Heap size is the answer.

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

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) {
  if (!intervals.length) return 0;
  intervals.sort((a, b) => a[0] - b[0]);
  const heap = new MinHeap();
  for (const [start, end] of intervals) {
    if (heap.size() && heap.peek() <= start) heap.pop();
    heap.push(end);
  }
  return heap.size();
}

Tradeoff:

2. Two sorted arrays (sweep line)

Separate start and end times into two sorted arrays. Sweep with two pointers: increment count on each start, decrement on each end (when end <= start). Track max count.

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, e = 0;
  for (let s = 0; s < starts.length; s++) {
    if (starts[s] >= ends[e]) { rooms--; e++; }
    rooms++;
    maxRooms = Math.max(maxRooms, rooms);
  }
  return maxRooms;
}

Tradeoff:

Square-specific tips

Square Appointments is a real product so this problem carries domain weight in your interview. Interviewers want you to map the algorithm back to the product: 'room count = number of concurrent POS terminals or staff slots needed.' The two-sorted-arrays approach tends to land better in a code review because it avoids a heap implementation — but be ready to code the heap if they push for it as a data-structures check.

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

Practice these live with InterviewChamp.AI →