Meeting Rooms II — Minimum Conference Rooms via End-Time Heap

Problem Statement#

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

Constraints:

• 1 <= intervals.length <= 10^4
• 0 <= starti < endi <= 10^6

Examples:

Input:  intervals = [[0,30],[5,10],[15,20]]
Output: 2
 
Explanation:
  Room 1: [0,30]
  Room 2: [5,10], then [15,20]
  Two rooms are sufficient.

Input:  intervals = [[7,10],[2,4]]
Output: 1
 
Explanation: These meetings don't overlap. One room is enough.

Input:  intervals = [[1,5],[2,6],[3,7],[4,8]]
Output: 4
 
Explanation: All four meetings overlap, requiring 4 rooms.

Why This Problem Matters#

Meeting Rooms II is one of the most practical and commonly asked interval problems at FAANG companies. Facebook, Amazon, Google, and Microsoft all include it in their interview pools because it models a real-world resource allocation problem: how many parallel resources (conference rooms, servers, threads, CPU cores) are needed to handle a set of overlapping requests?

The answer — a min-heap of end times — teaches the key insight that you don't need to track which room is which, only when each room becomes available. This abstraction drives elegant code and generalizes to many resource scheduling problems.

There are three common approaches to this problem:

1. Min-heap of end times — O(n log n), the expected interview answer.
2. Chronological event sweep (two sorted arrays) — O(n log n), conceptually elegant.
3. Chronological sorting with two pointers — O(n log n), very concise.

The min-heap approach is preferred because it naturally models the thought process: when a new meeting starts, check if any room is free (the room with the earliest end time is free if its end time ≤ new start time). If free, reuse that room; otherwise, allocate a new one.

This problem also teaches the general pattern of interval scheduling with resources: sort by start time, track resource availability with a heap of end times.

The Core Insight#

Sort meetings by start time. Maintain a min-heap of end times of currently occupied rooms.

When processing meeting [start, end]:

• The heap root is the room that becomes free the earliest.
• If heap[0] <= start, that room is available — reuse it by replacing its end time with the new meeting's end time (heapreplace).
• If heap[0] > start, all rooms are still busy — allocate a new room (push the new end time).

The heap size at the end equals the number of rooms used = the minimum rooms required.

Key insight: The heap size never decreases (we only add rooms). At any point, the heap size represents the number of rooms currently allocated. The answer is the maximum heap size reached... but wait, since we only add rooms, the final heap size is the maximum.

Actually, we do reuse rooms (heapreplace). So the heap size can stay stable when we reuse. The final heap size represents the total rooms allocated across the entire schedule.

intervals = [[0,30],[5,10],[15,20]], sorted by start
 
Process [0,30]: heap empty → push 30 → heap=[30], rooms=1
Process [5,10]: heap=[30], 30 > 5 → push 10 → heap=[10,30], rooms=2
Process [15,20]: heap=[10,30], 10 ≤ 15 → reuse → heap=[20,30], rooms still 2
 
Final heap size = 2. Answer = 2.

Visual Dry Run#

Input: intervals = [[2,11],[6,16],[11,16]]

Sorted by start: [[2,11],[6,16],[11,16]]

Final heap size = 2. Answer = 2.

Chronological event sweep alternative:

Create events: (time, type) where type +1 = meeting starts, -1 = meeting ends. Sort by time (tie: -1 before +1, i.e., end before start). Scan events, track running count.

Events: (0,+1),(5,+1),(10,-1),(15,+1),(20,-1),(30,-1)
Running: 0→1→2→1→2→1→0  → max = 2

Solution (Optimal)#

import heapq
 
def minMeetingRooms(intervals: list[list[int]]) -> int:
    # Sort meetings by start time
    intervals.sort(key=lambda x: x[0])
 
    heap = []   # min-heap of end times of occupied rooms
 
    for start, end in intervals:
        if heap and heap[0] <= start:
            # Earliest-ending room is free — reuse it
            heapq.heapreplace(heap, end)
        else:
            # No room available — allocate new one
            heapq.heappush(heap, end)
 
    return len(heap)    # total rooms allocated
 
# Two-pointer chronological sweep: O(n log n), same complexity
def minMeetingRoomsChronological(intervals: list[list[int]]) -> int:
    starts = sorted(s for s, e in intervals)
    ends = sorted(e for s, e in intervals)
 
    rooms = 0
    j = 0   # pointer into ends
    for start in starts:
        if start >= ends[j]:
            # A meeting ended before this one starts → reuse room
            j += 1
        else:
            # Need a new room
            rooms += 1
 
    return rooms

function minMeetingRooms(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
 
    // Min-heap of end times using sorted array for interview clarity
    const endTimes = [];
 
    const heapPush = (val) => {
        let lo = 0, hi = endTimes.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (endTimes[mid] < val) lo = mid + 1;
            else hi = mid;
        }
        endTimes.splice(lo, 0, val);
    };
 
    for (const [start, end] of intervals) {
        if (endTimes.length > 0 && endTimes[0] <= start) {
            endTimes.shift();   // reuse earliest-ending room
        }
        heapPush(end);      // assign this meeting to a room
    }
 
    return endTimes.length;
}

Complexity Analysis:

Sorting is O(n log n). Each meeting involves one push or heapreplace (O(log n)). Total: O(n log n).

The chronological sweep approach uses two sorted arrays and two pointers, achieving O(n log n) with O(n) space and very clean code — often the shortest valid solution.

Common Mistakes#

• Using < instead of <= when checking if a room is free. If heap[0] == start, the room's previous meeting ended exactly when the new one starts. The room is free (meetings don't overlap). Use heap[0] <= start.
• Not sorting by start time first. The heap approach relies on processing meetings in start-time order. Without sorting, the heap comparisons are meaningless.
• Thinking heap size fluctuates and finding the max. The heap size can only stay stable (on reuse) or increase (on new room allocation). It never decreases — so the final heap size is the maximum, which is the answer.
• Using a max-heap instead of min-heap. You want the room that becomes free the soonest (earliest end time) to check if it's available. This requires a min-heap.
• Confusing "rooms required" with "meetings count." The answer is the peak number of simultaneous meetings, not the total meeting count.

Follow-up Questions#

• What if you need to return which meetings go in which room? Track (end_time, room_id) in the heap. Assign room IDs starting from 0 and record assignments.
• What if meetings have priorities and you want to maximize total priority within a room count limit? This becomes a scheduling optimization problem — use DP with the room count as a constraint.
• How does this extend to k-resource scheduling? If you have at most k rooms, process meetings in start-time order and check if fewer than k rooms are in use. If yes, schedule in any available room.
• What is the event-sweep approach's advantage? It avoids an explicit heap and uses two sorted arrays, which is easier to implement and explain in some interview contexts.
• What if end times can equal start times of other meetings? The <= condition handles this: a meeting ending at time T can immediately be followed by a meeting starting at T in the same room.

Key Takeaways#

• Sort meetings by start time first; a min-heap of end times then gives O(n log n) with O(n) space.
• The heap root represents the room that becomes free soonest — if its end time is <= new start, reuse it; otherwise allocate a new room.
• Use heap[0] <= start (not strictly less than): a room ending exactly at the new meeting's start is available.
• Final heap size equals total rooms allocated — it never decreases since heapreplace swaps rather than shrinks.
• The two-sorted-arrays sweep approach achieves the same O(n log n) with O(n) space and often shorter code.
• Meeting Rooms II is the canonical "minimum resources for concurrent tasks" template — applies to CPUs, servers, and delivery trucks.
• FAANG companies use this to test interval scheduling intuition; always name both approaches and explain the heap invariant.