Day 25/365: Meeting Rooms II -- Counting Overlap, Not Merging It

365 Day DSA & System Design Challenge

A customer walked into one of our four conference rooms at 2pm with a confirmation. Someone else was already there, also confirmed, for the same room at the same time. The booking system had accepted a fifth concurrent booking when we only owned four rooms. The bug was not a race condition or a missing lock. It was an algorithm choice: the capacity check ran merge intervals, and merge intervals answers the wrong question.

What merge intervals actually computes

Merge intervals takes a list of [start, end) ranges, sorts them by start, and fuses any that touch or overlap into combined spans. The output is a smaller set of disjoint ranges -- the union of busy time.

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:                 # overlaps the previous span
            merged[-1] = (last[0], max(last[1], end))
        else:
            merged.append((start, end))
    return merged

That is perfect when you want "the blocks of the day where at least one booking exists." But notice what it throws away. Feed it five meetings that all overlap and it returns one span. The number five is gone. To a downstream capacity check, one meeting and five stacked meetings look identical: both are a single busy block.

The question capacity actually asks

Capacity planning is a peak question, not a union question. Across the whole day, what is the largest number of bookings alive at the same instant? That maximum simultaneous count is the number of rooms you must own. This is LeetCode 253, Meeting Rooms II, and it generalizes to peak concurrent database connections, simultaneous downloads, or checkout lanes at the busiest minute.

Solution 1: two-pointer sweep over separate sorted arrays

The mental model is a sweep line. Walk the timeline left to right; each start raises the live count, each end lowers it; the answer is the highest the count ever reaches. You only need the start times in order and the end times in order -- the pairing does not matter.

def min_rooms_two_pointer(intervals):
    if not intervals:
        return 0
    start_times = sorted(iv[0] for iv in intervals)
    end_times = sorted(iv[1] for iv in intervals)
    in_use, most = 0, 0
    si = ei = 0
    total = len(intervals)
    while si < total:
        if start_times[si] < end_times[ei]:
            in_use += 1
            most = most if most >= in_use else in_use
            si += 1
        else:
            in_use -= 1
            ei += 1
    return most

The strict < is load-bearing. With half-open intervals, a room freed at exactly 10:00 is available to a 10:00 booking, so when a start ties an end, the end must win and free the room first. Flip the comparison and you over-allocate.

Solution 2: min-heap of end times

The heap version makes the rooms tangible. Sort by start, hold a min-heap of the end times of rooms currently in use. The smallest end time is the room that frees up soonest.

import heapq

def min_rooms_heap(intervals):
    if not intervals:
        return 0
    ordered = sorted(intervals, key=lambda iv: iv[0])
    occupied = []                            # min-heap of end times
    for begin, finish in ordered:
        if occupied and occupied[0] <= begin:
            heapq.heappushpop(occupied, finish)  # the soonest room freed -> reuse it
        else:
            heapq.heappush(occupied, finish)     # nothing free -> new room
    return len(occupied)

The heap's size at any moment is the number of rooms in use, and its maximum (here, its final size, since we never pop without pushing) is the answer. Both solutions are O(n log n) because of the sort.

The one-sentence test

Before writing anything on an interval problem, ask: do I want the busy spans, or the peak number of things busy at once? If the output is a list of ranges, merge. If the output is a single capacity number, sweep the boundaries and track the running maximum. Both problems start from "a list of intervals" and both involve the word "overlap," which is exactly why they feel like one problem with two flavors. They are two problems. One collapses overlaps into a union; the other counts them at their peak.

What I shipped

The production fix was small once the diagnosis was right: replace the merge with the two-pointer sweep, compare the peak against the four physical rooms, and reject any booking that would push the peak past capacity. The double-booking stopped that afternoon. The takeaway I am keeping is that "overlapping intervals" is a fork, not a single pattern, and the word "overlap" hides which branch you are on.

Day 25/365 of the 365 Day DSA & System Design Challenge.