Meeting Rooms II — InterviewPrepKit

Solving tips

The answer is peak concurrency (max simultaneous meetings), and that peak only occurs at a meeting's start time.
Sort by start and keep a min-heap of end times: if the earliest end <= new start reuse that room (heapreplace), else push a new one; the heap size is the answer.
Alternative with no heap: sort all starts and all ends separately and two-pointer sweep, doing +1 per start and processing frees (end <= start) before each increment.
Boundary: a room ending at t is free for a meeting starting at t, so use '<=' in the free-room test; both approaches are O(n log n) time, O(n) space.

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

Hint 1

The answer is the peak number of simultaneously running meetings. When can that peak occur — at arbitrary times, or only at moments when some meeting starts?

Hint 2

Process meetings sorted by start. For each new meeting, you need to know one thing: has any currently running meeting already finished? Which running meeting should you check first, and what data structure serves that up cheaply?

Hint 3

Two classic routes: (a) keep a min-heap of end times — pop the earliest end if it's ≤ the new start, then push the new end; the heap's peak size is the answer. (b) Sort all starts and all ends separately and advance two pointers, +1 room per start not matched by an earlier end.

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

class Solution:
    def minMeetingRooms(self, 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 hands you exactly that room in O(log n).

import heapq
from typing import List

class Solution:
    def minMeetingRooms(self, 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):

[0,30]: heap empty → push 30. Heap [30], 1 room.
[5,10]: earliest end is 30 > 5 → no room free → push 10. Heap [10, 30], 2 rooms.
[15,20]: earliest end is 10 <= 15 → reuse that room, replace 10 with 20. Heap [20, 30], still 2 rooms.
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. Strip the intervals into two independent sorted arrays, all starts and all ends, and replay time: each start is +1 room unless some end has already occurred to offset it.

from typing import List

class Solution:
    def minMeetingRooms(self, 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].

s = 1: no end <= 1 → rooms = 1.
s = 2: earliest end 4 > 2 → rooms = 2.
s = 3: earliest end 4 > 3 → rooms = 3.
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.