Meeting Rooms, in depth: numbered rooms with delays, online booking, k-overlap limits and why capacity breaks the greedy

Recap: the room count

Meetings are half-open intervals [start, end): a meeting ending at 10:00 and one starting at 10:00 can share a room. The minimum number of rooms keeps a min-heap of end times; each meeting, in start order, reuses the room that frees earliest if it is free by then:

import heapq

def min_rooms(meetings):
    ends = []                                  # end times of rooms in use
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:          # half-open: <= frees the room
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)
    return len(ends)

The count is optimal because the heap only grows when every room is busy at this start time, which means that many meetings overlap at one instant. In graph terms the room count is the clique number of the interval graph, which equals its chromatic number; Interval Graphs, in depth proves why.

Numbered rooms and delayed meetings

Now fix the number of rooms n, numbered 0 to n - 1, and change the rule. Each meeting takes the lowest-numbered free room. If no room is free, the meeting waits for the earliest room to free and then runs for its original duration; waiting meetings go in order of their original start. The question is which room hosts the most meetings, ties to the lowest number. This is the rule set of the well-known Meeting Rooms III problem, and it models a real policy: first come, first served, never reject.

Two heaps implement it. The free heap holds room numbers. The busy heap holds (end, room) pairs. Before placing a meeting, move every room whose end is at or before the meeting's start into the free heap.

def most_booked(n, meetings):
    free = list(range(n))               # already a valid min-heap
    busy = []                           # (end, room)
    count = [0] * n
    for start, end in sorted(meetings):
        while busy and busy[0][0] <= start:
            heapq.heappush(free, heapq.heappop(busy)[1])
        if free:
            room = heapq.heappop(free)
            heapq.heappush(busy, (end, room))
        else:
            when, room = heapq.heappop(busy)          # earliest end, lowest room on ties
            heapq.heappush(busy, (when + end - start, room))
        count[room] += 1
    return max(range(n), key=lambda r: (count[r], -r))

Trace three rooms and meetings [1,20), [2,10), [3,5), [4,9), [6,8). The first three take rooms 0, 1, 2. At time 4 no room is free; room 2 frees first (at 5), so [4,9) becomes [5,10) in room 2. At time 6 nothing has freed; rooms 1 and 2 both end at 10, the tuple order picks room 1, and [6,8) becomes [10,12). Room counts are 1, 2, 2, so the answer is room 1.

Details that break the simulation

• Ties need the tuple. Storing (end, room) makes the busy heap break end-time ties by room number, which is exactly the lowest-number rule. Storing end alone loses it.
• A delayed meeting starts when its room frees. Its new end is that room's end plus the meeting's duration, not its original end; using the original end lets later meetings overlap it.
• Delays accumulate. End times grow beyond any input value. With 100,000 meetings of length up to 500,000, ends can exceed 32-bit range, so use 64-bit integers in Java or C++.
• Equal start times. The rule assumes unique starts; if yours can tie, define the order (submission time, then id) before sorting.

Which room policy, and what it changes

Lowest number first is one policy among several. A building may prefer the least-used room to spread wear, or a round-robin to keep cleaning crews busy evenly. With identical rooms, the choice does not change when meetings run. The simulation's state that matters for timing is the multiset of busy end times plus the number of free rooms, and picking one free room over another leaves both unchanged; a delayed meeting always takes the earliest end time, whichever room holds it. So every meeting starts at the same time under every such policy, and only the per-room counts differ.

That has a practical consequence: you can tune the room-choice policy for fairness, maintenance or proximity without re-validating delays, and you can test the claim directly by running the simulation with a random free-room choice and comparing start times, which is how it was checked here. The invariance ends as soon as rooms differ, which is the next problem.

Online booking

A calendar answers requests one at a time: can this booking go in, and if so, record it. For a single room, keep bookings sorted by start and check only the two neighbours of the insertion point:

from bisect import bisect_right

class RoomCalendar:
    def __init__(self):
        self.starts, self.ends = [], []

    def book(self, start, end):
        i = bisect_right(self.starts, start)
        if i > 0 and self.ends[i - 1] > start:              # previous runs into us
            return False
        if i < len(self.starts) and self.starts[i] < end:   # we run into next
            return False
        self.starts.insert(i, start)
        self.ends.insert(i, end)
        return True

Lookup is O(log n); Python list insertion is O(n), which is fine for a room's calendar. A balanced tree (Java's TreeMap with floorKey and ceilingKey) makes both logarithmic.

Some resources allow overlap up to a limit k: a studio that can host two sessions, a GPU node that can hold three jobs. A booking is valid if no instant would have more than k bookings in progress. Sweep the bookings that overlap the request:

class LimitedCalendar:
    def __init__(self, k):
        self.k, self.booked = k, []

    def book(self, start, end):
        events = [(start, 1), (end, -1)]
        for s, e in self.booked:
            if s < end and start < e:                 # overlaps the request
                events += [(s, 1), (e, -1)]
        live = 0
        for _, delta in sorted(events):               # (t, -1) before (t, +1)
            live += delta
            if live > self.k:
                return False
        self.booked.append((start, end))
        return True

Sorting (t, -1) before (t, +1) is what makes the sweep half-open. This costs O(n log n) per request. At scale, keep a segment tree over discretised time with range add and range maximum: check max on [start, end) below k, then add 1.

Rooms with capacities

Give rooms capacities and meetings sizes; a meeting may only use a room at least its size. The natural greedy processes meetings by start and gives each the smallest free room that fits, saving big rooms for big meetings. It is not optimal. Two rooms, Small (4 seats) and Large (12):

The greedy filled Small with A, which forced B into Large, which blocked C. The exchange argument behind the count no longer works because rooms are not interchangeable: swapping two meetings' rooms may violate a capacity. Choosing by smallest fit at start time cannot see that a later large meeting will need the big room while a small meeting still holds it.

For a single building's daily schedule, an exact search is cheap. Order meetings by start, try the rooms that fit from smallest to largest, and backtrack when a meeting has no candidate:

def assign_exact(rooms, meetings):
    """rooms: {name: capacity}; meetings: (start, end, size, id). None if impossible."""
    order, plan = sorted(meetings), {}
    busy = {room: [] for room in rooms}

    def free(room, s, e):
        return all(e2 <= s or e <= s2 for s2, e2 in busy[room])

    def place(i):
        if i == len(order):
            return True
        s, e, size, mid = order[i]
        for room in sorted(rooms, key=rooms.get):        # smallest fit first
            if rooms[room] >= size and free(room, s, e):
                busy[room].append((s, e)); plan[mid] = room
                if place(i + 1):
                    return True
                busy[room].pop(); del plan[mid]          # undo and try the next room
        return False

    return dict(plan) if place(0) else None

On the example it returns A in Large, B in Small and C in Large. Because it tries the smallest fit first, its first path is the greedy, and it only backtracks when the greedy would fail. The worst case is exponential, so for large inputs write it as an integer programme with a binary variable per (meeting, eligible room) and one constraint per room and set of mutually overlapping meetings, or run the greedy first and the exact search only on the meetings it could not place. Always measure how often the fallback fires.

Production concerns

• Store UTC, display local. Daylight-saving changes create local times that occur twice or never; overlap tests on local times break on those days.
• Buffers are part of the interval. If rooms need ten minutes of cleaning, extend each booking's end before every overlap check, not only in the UI.
• Recurring meetings. Expand the series over the booking horizon and check every occurrence; report which ones conflict instead of rejecting the whole series.
• Concurrent requests. Two users checking the same slot at once will both see it free. Let the database enforce it: PostgreSQL can reject overlapping rows with an exclusion constraint such as EXCLUDE USING gist (room_id WITH =, during WITH &&) on a range column (the equality part needs the btree_gist extension).

Failure modes

• Closed intervals by accident. Using < where <= was meant counts back-to-back meetings as overlapping and wastes a room.
• Heap of ends without room ids. Fine for counting, useless for assignment and wrong for lowest-number rules.
• Trusting the capacity greedy. It fails on three meetings, as shown; never present it as optimal.
• Integer overflow on delayed ends. Accumulated delays exceed 32-bit range on large inputs.

Trade-offs

The two-heap simulation is O(n log n) and exactly encodes a first-come policy, but it optimises nothing; a different policy, such as best fit by duration, needs a different simulation. Sorted-list calendars are simple and fast per room; the k-limit sweep is simple but linear per request, and the segment tree is fast but needs discretised time. Capacity-aware assignment trades the greedy's speed for exactness; a hybrid keeps the common case fast. For room counts on equal rooms, the plain heap remains optimal and should stay your default.

Testing cost is the trade-off people skip. Each variant here is a few dozen lines, and each has an off-by-one waiting at the boundary between one meeting's end and the next one's start. A brute-force checker that marks every integer instant on small random inputs takes ten minutes to write and catches those bugs before users do; keep it in the test suite next to the fast version.

What to do next

1. Fix the half-open convention and write it next to every comparison.
2. Implement min_rooms and most_booked, and test both against a brute-force simulator on small random inputs.
3. Pick the booking structure: neighbour check for one room, the k-limit sweep or a segment tree for shared resources.
4. If rooms differ in capacity, add an exact fallback and measure how often the greedy needs it.
5. Enforce non-overlap in the database with an exclusion constraint, not only in application code.
6. Read Activity Selection, in depth for the case where you must drop meetings instead of delaying them.