Meeting Rooms II

Signal

"Minimum resources to cover the worst-case simultaneous overlap" is a max concurrency question — separate the starts from the ends, sort each, and sweep across time counting how many meetings are open at once.

Approach

Split the intervals into two sorted lists: all start times and all end times. Walk both with two pointers, advancing whichever timestamp is smaller. Every start you consume opens a room (increment a running count); every end you consume before or at the next start frees one (decrement). The answer is the maximum the running count ever reaches.

Skeleton

starts = sorted(all starts)
ends = sorted(all ends)
s = e = rooms = max_rooms = 0
while s < len(starts):
    if starts[s] < ends[e]:
        rooms += 1; s += 1
    else:
        rooms -= 1; e += 1
    max_rooms = max(max_rooms, rooms)

Solution

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

    s = e = 0
    rooms = 0
    max_rooms = 0

    while s < len(starts):
        if starts[s] < ends[e]:
            rooms += 1
            s += 1
        else:
            rooms -= 1
            e += 1
        max_rooms = max(max_rooms, rooms)

    return max_rooms

Complexity

O(n log n) time — sorting both lists dominates; the two-pointer sweep is O(n). O(n) space for the separated start/end lists.

Pitfalls

• Comparing starts[s] < ends[e] (strict) means a meeting starting exactly when another ends does not need a new room — they don't count as overlapping at a shared boundary instant. Using <= here overcounts rooms.
• Separating starts and ends loses which end belongs to which start — that's fine, since only the count of concurrent meetings matters, not which specific meeting occupies which room.
• The min-heap-of-end-times approach is equivalent and worth knowing too: push each meeting's end, and before pushing a new one, pop-and-reuse the heap's smallest end if it's <= the new meeting's start; heap size at the end is the answer.