Interval Merging + Meeting Rooms, in depth: half-open intervals, merge, the room count three ways, room assignment and production traps

The picture

First principles: what an interval means

An interval is a pair (start, end) with start no later than end. Before writing any code, decide what the end means. There are two common conventions. A closed interval [s, e] contains both endpoints. A half-open interval [s, e) contains s but not e. Calendars almost always mean half-open: a meeting from 09:00 to 10:00 and one from 10:00 to 11:00 do not clash, and you can book them back to back in the same room.

With half-open intervals, a and b overlap exactly when a.start < b.end and b.start < a.end. With closed intervals, both comparisons become <=. That single character decides whether back-to-back meetings need one room or two. Half-open intervals also have length end minus start, and split cleanly at any m into [s, m) and [m, e).

Pick half-open, store times as integers in one unit and one timezone (UTC epoch seconds or minutes), and convert only at the edges of the system. Everything below assumes that.

Merging intervals

Merging takes a set of intervals and returns their union as disjoint blocks: the busy time of a calendar, the covered ranges of a file, the set of IP addresses already allocated. The algorithm is short:

def merge(intervals):
    """Union of half-open intervals, as a sorted list of disjoint [start, end)."""
    out = []
    for s, e in sorted(intervals):            # sort by start (then end)
        if out and s <= out[-1][1]:           # overlaps or touches the last block
            out[-1][1] = max(out[-1][1], e)   # extend; never shrink
        else:
            out.append([s, e])                # gap: start a new block
    return out

Why sorting by start is enough. After sorting, keep the invariant that out holds the union of everything seen so far as ordered disjoint blocks. The next interval (s, e) starts no earlier than any previous one. If s lies beyond the last block's end, no later interval can bridge that gap, because they all start at s or after, so the last block is final and a new one opens. Otherwise (s, e) extends the last block. Only the last block ever changes, so one pass is correct.

Two details matter. First, max(out[-1][1], e) is essential: a nested interval must not cut the block short. Forgetting it is the classic bug. Second, the <= here merges touching blocks such as [9, 10) and [10, 11) into [9, 11). For busy time that is what you want, since the union is contiguous. If you need to keep separate bookings visible, use < instead, and write down which one you chose.

Cost: O(n log n) for the sort and O(n) for the scan. Input that already arrives sorted, for example from an index range scan, merges in O(n) as a stream.

Meeting rooms: the minimum room count

The easy form asks whether one person can attend every meeting: sort by start and check each meeting against the previous end. The interesting form asks for the minimum number of rooms.

The key fact: the answer equals the maximum number of meetings in progress at any single instant. It cannot be less, because at that instant every live meeting needs its own room. It is never more, because the greedy below never opens a room unless every existing room is occupied at that moment, which means that many meetings really are live together.

That gives two implementations with the same answer:

import heapq

def min_rooms_heap(meetings):
    """Fewest rooms so no two overlapping half-open meetings share one."""
    ends = []                                   # min-heap of end times, one per busy room
    for s, e in sorted(meetings):
        if ends and ends[0] <= s:               # earliest-ending room is free by s
            heapq.heapreplace(ends, e)          # reuse it
        else:
            heapq.heappush(ends, e)             # every room busy: open another
    return len(ends)

def min_rooms_sweep(meetings):
    """Same answer as the peak number of simultaneous meetings."""
    events = [(s, +1) for s, e in meetings] + [(e, -1) for s, e in meetings]
    events.sort()                               # at equal times -1 sorts before +1
    live = best = 0
    for _, delta in events:
        live += delta
        best = max(best, live)
    return best

The heap holds the end time of each room's current meeting; its minimum is the room that frees first. Reuse it if it is free by the next start, otherwise open a room. Cost: O(n log n) plus O(n log k) for k rooms.

The sweep version does not simulate rooms at all. It turns every meeting into a +1 event at its start and a -1 event at its end, sorts, and tracks the running total. The (time, delta) tuples sort -1 before +1 at equal times, which is exactly the half-open rule: a meeting that ends at 10:00 releases its slot before one that starts at 10:00 takes it. The popular variant with two separately sorted arrays of starts and ends is the same sweep, merged by hand.

Give each event a weight instead of 1 and the sweep computes peak bandwidth or peak memory of overlapping jobs. The heap generalises the other way: it knows which room is which.

Worked example: six meetings, traced

Take six meetings for one morning, in minutes but shown as clock times: A 09:00 to 10:00, B 09:30 to 11:00, C 10:00 to 10:30, D 10:30 to 12:00, E 11:00 to 11:30 and F 13:00 to 14:00.

Merging gives two busy blocks: 09:00 to 12:00 and 13:00 to 14:00. A and B overlap into 09:00 to 11:00, C sits inside it, D extends it to 12:00, E sits inside it and F stands alone.

The sweep produces these live counts: 1 at 09:00, 2 at 09:30; at 10:00 A's end is processed before C's start, so the count dips to 1 and returns to 2, as it does again at 10:30 and 11:00; then 1 at 11:30, 0 at 12:00, 1 at 13:00 and 0 at 14:00. The peak is 2, so two rooms suffice.

The heap agrees: A and B open two rooms (heap [10:00, 11:00]); C at 10:00 finds the earliest end equal to its start and reuses that room, and so do D, E and F. The heap never grows past two.

Now introduce the classic bug. Treat the intervals as closed by sorting ends after starts at equal times. Running that variant on the same six meetings reports 3 rooms, because at 10:00, 10:30 and 11:00 the starting meeting is counted before the ending one leaves. One tie-breaker costs a room.

Assigning rooms, not just counting them

Counting rooms is rarely the end. A booking system has to say which room each meeting gets, and users notice if their weekly meeting hops between rooms for no reason. Keep two heaps: busy rooms keyed by end time, and free room ids keyed by id. Before placing a meeting, release every room whose meeting has ended by its start; then take the lowest free id, or open a new one.

def assign_rooms(meetings):
    """Return a room number per meeting, reusing the lowest free room id."""
    free, busy, next_id = [], [], 0             # free: heap of ids; busy: heap of (end, id)
    room = [None] * len(meetings)
    for i, (s, e) in sorted(enumerate(meetings), key=lambda t: t[1]):
        while busy and busy[0][0] <= s:         # release every room free by s
            _, r = heapq.heappop(busy)
            heapq.heappush(free, r)
        if free:
            r = heapq.heappop(free)
        else:
            r, next_id = next_id, next_id + 1
        room[i] = r
        heapq.heappush(busy, (e, r))
    return room

On the six meetings this returns rooms 0, 1, 0, 0, 1, 0 for A to F, which is the layout in the diagram. Releasing all finished rooms first and then taking the lowest id makes the result deterministic, so the same input always produces the same layout. That matters for tests, for caching and for explaining a schedule to a user. It still uses the minimum number of rooms, because a new id is opened only when no released room exists. Once rooms differ in capacity or equipment, the greedy no longer guarantees a minimum; treat it as a heuristic and measure it.

Variants you will meet

Most interval questions in production are one of a handful of variants of these two moves.

• Common free time. Merge every person's busy intervals together, then report the gaps between consecutive blocks inside the working day. This is how a find-a-slot feature works, and it is just merge plus one more pass.
• Intersection of two schedules. Two sorted, disjoint lists intersect with two pointers in linear time: emit the overlap of the current pair, then advance whichever ends first.
• Fewest removals to make intervals disjoint. Sort by end, not start, and keep each interval that starts after the last kept one ends. That is activity selection, and its exchange-argument proof is in Greedy Algorithms, in depth.
• Peak load over integer time. With small integer coordinates, a difference array (add 1 at start, subtract 1 at end, prefix-sum) replaces the sort. With range updates and range-maximum queries arriving online, use a segment tree with lazy propagation.
• Online stabbing and overlap queries. When intervals arrive and leave continuously and you need every booking that overlaps a new request, re-sorting per query is too slow. An interval tree answers that in O(log n + k).

Deadline-driven scheduling, where each job has a profit and must finish by a deadline, looks related but is a different problem with different greedy rules; see Job Scheduling with Deadlines.

Production concerns

The algorithms are a dozen lines. The bugs live around them.

Comparators. In Java, the widely copied comparator (a, b) -> a[0] - b[0] silently overflows when the two values are more than about two billion apart, and the sort then returns a wrong order with no exception. Compare, do not subtract. Epoch milliseconds need long anyway.

// The stub-era comparator a[0] - b[0] overflows when the difference exceeds int range,
// e.g. a sentinel start of Integer.MIN_VALUE. Compare instead of subtracting.
Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0]));

// Epoch milliseconds do not fit in int at all: use long[] or a record.
record Slot(long start, long end) {}
slots.sort(Comparator.comparingLong(Slot::start).thenComparingLong(Slot::end));

Time zones and recurrence. Expand recurring events into UTC instants before merging; 09:00 local every Monday is not a fixed UTC offset across a daylight-saving change. Expand only inside a bounded query window with an instance cap, because an open-ended daily meeting is infinite.

Concurrency. Checking that a room is free and then booking it is a race. Enforce non-overlap where the write happens, with a database exclusion constraint or a conditional write. The algorithm proposes; storage decides what is committed.

Scale. Merge per shard (room, tenant or time bucket), then combine the sorted shard outputs with a k-way merge driven by a binary-heap priority queue.

Failure modes

• Missing max on extend. A nested interval truncates a block. Test with [1, 10) and [2, 3).
• Wrong tie order. Ends processed after starts at equal times over-count rooms, as the worked example showed (3 instead of 2).
• Mixed conventions. One service stores inclusive ends, another exclusive; merged results drift by one unit. Convert at the boundary and assert start < end on ingest.
• Zero-length intervals. A [10, 10) reminder overlaps nothing under half-open rules but still emits events in the sweep. Decide whether to drop them and test it.
• Mutating input. The merge above builds fresh lists. A common shortcut appends the caller's own interval object and then extends its end in place, which silently rewrites the caller's data. Copy before you extend when inputs are shared.

Trade-offs

The batch approaches are simpler and faster per item but recompute from scratch. Dynamic structures cost more code and memory and pay off only when queries and updates interleave.

What to do next

1. Write down your interval convention (half-open, UTC, integer unit) in the type that stores intervals, and assert start < end at construction.
2. Implement merge and the event sweep; test with nested, touching, identical and zero-length intervals, and with the six-meeting example (2 rooms, blocks 09:00 to 12:00 and 13:00 to 14:00).
3. Add a property test: for random inputs, the heap count, the sweep peak and a brute-force maximum over all start times must agree.
4. Replace any subtracting comparator with Integer.compare or Comparator.comparingLong.
5. Enforce non-overlap at the storage layer, not only in application code.
6. Bound recurrence expansion by a query window and an instance cap.
7. If inserts and queries interleave at high rates, measure an interval tree against re-sorting before switching.