Meeting Rooms II — Heap and Sweep Line

The Problem

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

Example: [[0,30],[5,10],[15,20]] returns 2. The first meeting overlaps with both of the others, so it needs its own room.

Intuition

There are two equally elegant solutions and they teach different lessons.

Min-heap of end times: sort meetings by start time, then walk through them. For each meeting, check the room that frees up earliest. If that room is free in time, reuse it. Otherwise, open a new one. A min-heap keyed on end time lets you peek at the earliest-freeing room in O(log n). The heap size equals the number of currently active meetings.

Sweep line: forget the meetings. Think only about events. Starts add a room, ends remove one. Sort starts and ends independently, then walk two pointers. Same O(n log n) complexity, no heap.

The boundary decision matters. If meeting A ends at 10 and meeting B starts at 10, do they share a room? The standard convention says yes — touching at an endpoint is fine. That is why the heap version uses rooms[0] <= start and the sweep version uses s >= ends[e]. If your interviewer says the boundary should not be shared, flip to strict.

Explanation with Example

Input: [[0,30],[5,10],[15,20]]. Heap version walkthrough:

1. [0,30]: heap empty, push 30. Heap: [30].
2. [5,10]: top is 30, not <= 5. Push 10. Heap: [10, 30].
3. [15,20]: top is 10, <= 15. Pop. Push 20. Heap: [20, 30].

Final size: 2.

time:   0     5    10    15    20    25    30
      |-----|-----|-----|-----|-----|-----|
A:      [================================)
B:            [-----)
C:                        [-----)

active: 1     2     1     2     1     1     0
                              ^
                        peak = 2 rooms

Code

import heapq

def min_meeting_rooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    rooms = []
    for start, end in intervals:
        if rooms and rooms[0] <= start:
            heapq.heappop(rooms)
        heapq.heappush(rooms, end)
    return len(rooms)

def min_meeting_rooms_sweep(intervals):
    if not intervals:
        return 0
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)
    rooms = max_rooms = 0
    e = 0
    for s in starts:
        if s >= ends[e]:
            rooms -= 1
            e += 1
        rooms += 1
        max_rooms = max(max_rooms, rooms)
    return max_rooms

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> rooms = new PriorityQueue<>();
        for (int[] iv : intervals) {
            if (!rooms.isEmpty() && rooms.peek() <= iv[0]) rooms.poll();
            rooms.offer(iv[1]);
        }
        return rooms.size();
    }
}

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end(),
             [](auto& a, auto& b){ return a[0] < b[0]; });
        priority_queue<int, vector<int>, greater<int>> rooms;
        for (auto& iv : intervals) {
            if (!rooms.empty() && rooms.top() <= iv[0]) rooms.pop();
            rooms.push(iv[1]);
        }
        return rooms.size();
    }
};

Edge Cases

• Empty input: return 0.
• All meetings identical: returns n — every meeting needs its own room.
• All meetings disjoint and back-to-back: returns 1.
• Negative or zero-length intervals: clarify, but the algorithms still work as long as start <= end.

Complexity Analysis

Both approaches are O(n log n) time. The heap uses O(n) extra space; the sweep line uses O(n) for the sorted event arrays.

Which approach to pick in an interview?

• “Design a calendar service”: heap. It generalizes to streaming events.
• “Max concurrent intervals”: sweep line. Shorter, more elegant.
• If you forget the heap API mid-interview: sweep line is your safety net.

Lead with the heap solution because the metaphor — rooms as objects, the heap as a priority queue of when they free up — maps onto real systems. Mention sweep line as a simpler alternative.

Related / Generalizations

• Car Pooling: sweep line where the increment is capacity, not 1.
• My Calendar III: streaming sweep with a sorted map of deltas.
• Skyline Problem: heap-based sweep with active heights.

Master both solutions and you will recognize this pattern in dozens of variants.