Meeting Rooms II

Problem

From a coding assessment (2026-10-13), where it was called “Minimum meeting rooms”. Same problem as LeetCode #253 Meeting Rooms II.

Given n meetings as [start, end], return the minimum number of rooms so that no two meetings in the same room overlap. A meeting ending at time t and one starting at t do not overlap, so they can share a room.

Example 1

Input:  meetingTimings = [[1, 4], [1, 5], [5, 6], [6, 10], [7, 9]]
Output: 2

Constraints

• 1 <= n <= 2 * 10^5
• 1 <= start <= end <= 2 * 10^6

Thinking

• Brute force idea: the busiest moment is always at some meeting’s start, so for each start s count the meetings with start <= s < end: $O(n^2)$. Too slow at $n = 2 \cdot 10^5$.
• Key insight: every meeting running at the same moment needs its own room, and rooms can be reused freely, so answer = peak number of overlapping meetings. To find the peak you don’t need to know which start goes with which end: two sorted timelines are enough, one for “a meeting begins” and one for “a room frees up”. Sweep them with two pointers.
• Tie rule: a meeting ending at 5 hands its room to one starting at 5, so at equal times the end is processed first (ends[j] <= s, not <).
• Edge cases to remember: a single meeting, touching meetings ([1,5], [5,6] → 1 room), identical meetings (all need separate rooms), one long meeting covering many short ones. Zero-length meetings (start == end, allowed by the constraints) are ambiguous: the sweep treats them as needing no room, the heap gives them one (see section 5).

Solution

Approach A — my version: sorted starts and ends, two pointers ✅ best practice

Complexity: Time $O(n \log n)$ (sorting; the loop is $O(n)$ because j only moves forward) · Space $O(n)$. j points at the earliest meeting that hasn’t ended yet. For each start, release every meeting with end <= s, then take a room for the new one and record the peak.

def min_meeting_rooms(meetings: list[list[int]]) -> int:
    starts = sorted(m[0] for m in meetings)
    ends = sorted(m[1] for m in meetings)

    rooms = max_rooms = j = 0
    for s in starts:
        # free every room whose meeting ended by this start time
        while j < len(ends) and ends[j] <= s:
            j += 1
            rooms -= 1
        rooms += 1
        max_rooms = max(max_rooms, rooms)
    return max_rooms

Approach B — brute force: count overlaps at every start

Complexity: Time $O(n^2)$ · Space $O(1)$. The peak is reached at some start time, so check each one. Only useful as a reference to test the others against.

def min_meeting_rooms_brute(meetings: list[list[int]]) -> int:
    return max(sum(a <= s < b for a, b in meetings) for s, _ in meetings)

Approach C — sort by start, min-heap of end times

Complexity: Time $O(n \log n)$ · Space $O(n)$. The heap holds the end time of every room in use. If the room that frees up earliest is free by this start, reuse it (pop), then push this meeting’s end. The heap’s final size is the answer. Same speed, slightly more code, and it extends naturally to “which room does each meeting get”.

import heapq

def min_meeting_rooms_heap(meetings: list[list[int]]) -> int:
    ends: list[int] = []                     # end times of rooms in use
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:        # earliest-ending room is free again
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)
    return len(ends)

Scratch / Experiments

Zero-length meetings

The constraints allow start == end. The sweep processes the end before the start at equal times, so a zero-length meeting gives its room back before taking it: it never counts. The heap always pushes it, so it gets a room. If the grader expects a room for every meeting, use the heap.

for meetings in ([[5, 5]], [[5, 5], [5, 5]], [[1, 10], [5, 5]]):
    print(meetings, {fn.__name__: fn(meetings) for fn in APPROACHES})

Timing

Max size $n = 2 \cdot 10^5$ random meetings for A and C; the brute force is $O(n^2)$, so it gets $n = 2000$, where it is already ~400× slower than the others.

Typical results:

A and C are both $O(n \log n)$ and tie at small $n$. At full size A is about twice as fast: it sorts two flat lists of ints (fast C comparisons) while C sorts lists of pairs (each comparison compares lists) and then does a Python-level heap operation per meeting.

import random

random.seed(0)
def random_meetings(n):
    out = []
    for _ in range(n):
        s = random.randint(1, 2_000_000 - 1)
        out.append([s, random.randint(s + 1, min(s + 50_000, 2_000_000))])
    return out

small, big = random_meetings(2000), random_meetings(200_000)
for fn in APPROACHES:
    print(f"{fn.__name__:26s} n=2000 ", end=" ")
    %timeit fn(small)
for fn in (min_meeting_rooms, min_meeting_rooms_heap):
    print(f"{fn.__name__:26s} n=2e5  ", end=" ")
    %timeit fn(big)

Takeaways

• Pattern: “how many things are active at the same time” / “minimum resources so nothing clashes” → peak overlap. Sort the start times and the end times separately and sweep with two pointers (or sort ±1 events). Pairing doesn’t matter, only the order of events. Decide the tie rule explicitly: end-before-start when touching intervals don’t overlap.
• Mistakes to avoid:
  • Using < instead of <= when releasing rooms: touching meetings would then need two rooms.
  • Assuming the input is sorted: both approaches sort first.
  • Not checking what the constraints allow: start <= end means zero-length meetings exist, and the sweep and the heap answer them differently.
• Alternatives: the min-heap (Approach C) when you also need to assign rooms; a difference array over the time range ($O(n + T)$, $T = 2 \cdot 10^6$) when times are small integers.
• Related problems: Meeting Rooms (#252, can one person attend all = peak ≤ 1), Merge Intervals (#56, sort by start), Non-overlapping Intervals (#435, greedy by end), Car Pooling (#1094, same sweep with passenger counts), My Calendar II (#731), Minimum Number of Arrows to Burst Balloons (#452).