Meeting Rooms II

Problem

You are given a list of meetings as half-open time ranges [start, end). Every meeting must be held in some conference room, and a room can host only one meeting at a time. A room frees up the instant its meeting ends, so a meeting starting at time t can reuse a room whose previous meeting ended at t. Return the minimum number of conference rooms needed to schedule all the meetings.

Equivalently: what is the maximum number of meetings that are ever in progress at the same moment?

Examples

• intervals = [[0,30],[5,10],[15,20]] → 2 — [0,30] occupies one room the whole time; [5,10] and [15,20] don’t overlap each other, so they share a second room.
• intervals = [[7,10],[2,4]] → 1 — the meetings never coexist.
• intervals = [[1,4],[2,5],[3,6]] → 3 — at time 3 all three are running at once.

Constraints

• 1 <= len(intervals) <= 10^4
• 0 <= start < end <= 10^6

10^4 meetings makes O(n^2) counting borderline; the expected solutions are O(n log n).

Think about it first

TL;DR

Min-heap of end times (or the two-pointer start/end sweep) — O(n log n) time, O(n) space.

Approach 1 — Brute force: count overlaps at every start

The number of rooms needed equals the peak number of simultaneous meetings, and that peak is always attained at some meeting’s start time (concurrency only increases at a start). So for every meeting, count how many meetings are running at the moment it starts, and take the max.

from typing import List

def minMeetingRooms(intervals: List[List[int]]) -> int:
    rooms = 0
    for i, (start_i, _) in enumerate(intervals):
        running = 0
        for start_j, end_j in intervals:
            if start_j <= start_i < end_j:
                running += 1
        rooms = max(rooms, running)
    return rooms

(Meeting i counts itself, since start_i <= start_i < end_i.)

Complexity: O(n^2) time, O(1) space.

At n = 10^4 that’s 10^8 comparisons — too slow in Python, and it repeats work that a single sort would eliminate.

Approach 2 — Sort + min-heap of end times

The insight: process meetings in start order and simulate room assignment. The only room worth checking for reuse is the one whose meeting ends earliest — if even that one isn’t free, none are. A min-heap keyed on end time returns that room in O(log n).

flowchart TD
    A[Next meeting, in start order] --> B{Heap non-empty and earliest end <= start?}
    B -- Yes --> C[Reuse that room: replace earliest end with this end]
    B -- No --> D[Open a new room: push this end]
    C --> A
    D --> A

import heapq
from typing import List

def minMeetingRooms(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda it: it[0])
    ends: List[int] = []  # min-heap of end times of occupied rooms
    for start, end in intervals:
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)  # reuse the freed room
        else:
            heapq.heappush(ends, end)     # need a new room
    return len(ends)

Walkthrough on [[0,30],[5,10],[15,20]] (already sorted by start):

1. [0,30]: heap empty → push 30. Heap [30], 1 room.
2. [5,10]: earliest end is 30 > 5 → no room free → push 10. Heap [10, 30], 2 rooms.
3. [15,20]: earliest end is 10 <= 15 → reuse that room, replace 10 with 20. Heap [20, 30], still 2 rooms.
4. Answer: heap size 2.

Complexity: O(n log n) time (sort + one heap op per meeting), O(n) space for the heap.

Approach 3 — Two pointers over sorted starts and ends

The insight: you never need to know which room a meeting uses — only the running count. Split the intervals into two sorted arrays, all starts and all ends, and sweep through time: each start adds a room unless some end has already occurred to offset it.

from typing import List

def minMeetingRooms(intervals: List[List[int]]) -> int:
    starts = sorted(s for s, _ in intervals)
    ends = sorted(e for _, e in intervals)
    rooms = best = 0
    e = 0
    for s in starts:
        while e < len(ends) and ends[e] <= s:
            rooms -= 1
            e += 1
        rooms += 1
        best = max(best, rooms)
    return best

Walkthrough on [[1,4],[2,5],[3,6]]: starts = [1,2,3], ends = [4,5,6].

1. s = 1: no end <= 1 → rooms = 1.
2. s = 2: earliest end 4 > 2 → rooms = 2.
3. s = 3: earliest end 4 > 3 → rooms = 3.
4. Peak is 3 — matching the example.

Pairing which start goes with which end doesn’t matter: only the counts of starts and ends before each moment do.

Complexity: O(n log n) time, O(n) space for the two arrays.

Common pitfalls

• Boundary reuse: a room ending at t is free for a meeting starting at t, so the tests are ends[0] <= start / ends[e] <= s. Using < overcounts rooms for back-to-back meetings.
• Sorting the intervals but comparing each new meeting against the most recently added room instead of the earliest-ending one — that’s what the heap ordering is for.
• Trying to reduce this to Meeting Rooms I logic (adjacent-pair checks) — pairwise non-overlap tells you if 1 room suffices, but it can’t count the peak.
• In the two-pointer version, popping ends with a separate loop after incrementing rooms — frees must be processed before the +1 or touching meetings inflate the peak.

Pattern takeaway

When an intervals problem asks “how many at once?” rather than “do any overlap?”, sort by start and maintain the set of active intervals — a min-heap on end time if you need to interact with the earliest-finishing one, or the decomposed starts/ends sweep if only the count matters. Peak concurrency is the size that active set reaches.