Meeting Rooms II: Minimum Rooms via Heap or Sweep

"Meeting Rooms II" shows up again and again in Meta, Google, Uber phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Merge Intervals pattern quickly and code it cleanly. Part 5 of 11 in the Merge Intervals arc.

The Problem

Given meeting time intervals, return the minimum number of conference rooms required. Among the most-reported interview questions at Meta and Google for years running — the answer is the peak number of simultaneously active meetings, and there are two canonical ways to compute it.

Input:  intervals = [[0, 30], [5, 10], [15, 20]]
Output: 2
[0, 30] runs concurrently with each of the others, which do not overlap each other.

Recognizing the Merge Intervals Pattern

Interval problems — scheduling, calendars, resource booking — almost all reduce to one move: sort by start (or end), then sweep once while comparing each interval against a running boundary. Overlap exists when the next start is at most the current end. Sort plus linear sweep, O(n log n), is the backbone of the entire family.

Rooms are a resource freed at end times and claimed at start times — allocation over sorted events. A min-heap of active end times models 'which room frees soonest'; alternatively, +1/−1 events sorted by time reduce it to a running-sum maximum. Knowing both is the expectation at senior level.

The Approach

Heap version: sort by start. For each meeting, if the earliest-ending room is free by the meeting's start, pop it (reuse); push the new end time either way. The heap's peak size is the answer.

Sweep version: split into start events (+1) and end events (−1), sort with ends before starts at equal timestamps (touching does not need a new room), and track the running maximum. Same O(n log n); the sweep generalizes better to 'max concurrent X' questions, and saying so earns range points.

Python Solution

import heapq


def min_meeting_rooms(intervals: list[list[int]]) -> int:
    """Minimum rooms so no two concurrent meetings share one."""
    if not intervals:
        return 0
    intervals.sort(key=lambda iv: iv[0])
    ends: list[int] = []                  # min-heap of active end times
    for start, end in intervals:
        if ends and ends[0] <= start:
            heapq.heappop(ends)           # earliest room frees in time: reuse
        heapq.heappush(ends, end)
    return len(ends)

Complexity

• Time: O(n log n) — sort plus one heap push (and at most one pop) per meeting
• Space: O(n) — the heap holds up to one end time per concurrent meeting

Interview Tips and Follow-Ups

• Why pop at most once per meeting? Because you only need a free room, not all free rooms — a subtle point interviewers use to probe understanding.
• The sweep-line variant answers the common extension 'at which time is the peak?' almost for free — know it.
• Assigning actual room numbers (not just counting) means pushing (end, room_id) and reusing popped ids — a frequent follow-up at Uber.

If this clicked, continue the Merge Intervals arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.