Assign appointments to rooms

01The design, in the six-step framework

1. Requirements and use cases

This is a phased question. It opens as "how many rooms do these appointments need", moves to "assign each appointment the smallest free room id", and ends with "which room was busiest" or "cap the rooms and evict by priority". The design must grow through those phases without a rewrite.

• Given appointments as [start, end) intervals, assign each one a room; a room may hold only non-overlapping appointments.
• When several rooms are free, choose the smallest room id, so the answer is deterministic.
• Report the busiest room (most appointments, ties to the smallest id).
• With a fixed number of rooms, reject an appointment when none is free, or evict a lower-priority one.
• Support adding appointments later, not only as one sorted batch.

Out of scope: people, calendars, recurrence. Constraints: n appointments must be placed in O(n log n); an online insert must be O(log n) or O(k) for k rooms; the tie-break rule is part of the contract and must be tested.

2. Core entities and relationships

• Appointment: an immutable interval with an id and a priority.
• Room: an id, its assigned appointments and the instant it becomes free.
• RoomAllocator: the scheduling API; it owns the rooms and the two heaps that make assignment fast.
• AssignmentPolicy: the tie-break and eviction rule, swappable.

The allocator composes its rooms: they exist only inside it. Rooms aggregate appointments, because an appointment that is evicted keeps its identity and can be re-assigned elsewhere.

3. Interfaces and key methods

from dataclasses import dataclass, field
from typing import Optional

@dataclass(frozen=True, order=True)
class Appointment:
    start: int
    end: int
    id: str = field(compare=False)
    priority: int = field(default=0, compare=False)

@dataclass
class Room:
    id: int
    free_at: int = 0
    appointments: list = field(default_factory=list)
    def can_host(self, appt: Appointment) -> bool:
        """A room is free for appt if its last appointment ended at or before appt.start."""
        return self.free_at <= appt.start
    def host(self, appt: Appointment) -> None:
        """Append and move free_at forward; caller guarantees can_host."""

class RoomAllocator:
    def __init__(self, room_count: Optional[int] = None) -> None:
        """None means unbounded rooms (phase one); an int caps them (phase three)."""
    def assign_all(self, appts: list) -> dict:
        """Sort by start, assign in order; returns appointment id to room id."""
    def assign(self, appt: Appointment) -> Optional[Room]:
        """Online insert for a start no earlier than any already assigned; None if rejected."""
    def busiest(self) -> Room:
        """Most appointments, ties broken by the smallest room id."""

Invariants: busy holds exactly the rooms whose free_at is in the future relative to the last processed start; free_ids holds every room not in busy; the two heaps partition the rooms. Appointments are processed in start order, which is what makes "pop all rooms whose end has passed" correct.

4. Design patterns and the choices behind them

Two heaps, not a scan

The force: for each appointment we need the smallest free room id, and "free" changes as time advances. A min-heap of busy rooms keyed by free_at releases rooms in end order; a min-heap of free ids gives the smallest id in O(log k). This is the priority queue pattern applied twice; a linear scan over rooms per appointment is correct but O(n·k), and the interviewer will ask for better once the first version works.

Interval ordering as the engine

Sorting by start and releasing rooms whose end is at or before the current start is the same sweep behind every meeting-rooms question. Writing it as "release, then take" keeps the half-open rule honest: an appointment starting exactly when another ends reuses the room.

Tie-break and eviction behind a policy

The force: phase two wants the smallest id; a later phase wants priority eviction when rooms are capped. AssignmentPolicy exposes pick and victim; the allocator calls them and never encodes the rule itself, a small strategy. The method design returns None for a rejection rather than raising, because rejection is an expected outcome in the capped phase, not an error.

5. Core flow and code

1. assign_all sorts appointments by start and feeds them to assign one by one.
2. assign pops every room from busy whose free_at is at or before the new start and pushes its id onto free_ids.
3. If free_ids is non-empty, policy.pick chooses an id (the smallest); otherwise, unbounded mode creates a new room, capped mode asks policy.victim for a lower-priority room to evict, or returns None.
4. The chosen room hosts the appointment and goes back into busy keyed by its new free_at.
5. busiest is a max over rooms by (count, −id).

import heapq
from typing import Optional

class SmallestIdPolicy:
    def pick(self, free_ids: list) -> int:
        return heapq.heappop(free_ids)        # heap gives the smallest id
    def victim(self, rooms: list, appt: Appointment) -> Optional["Room"]:
        return None                          # phase two: never evict

class PriorityEvictionPolicy(SmallestIdPolicy):
    def victim(self, rooms: list, appt: Appointment) -> Optional["Room"]:
        candidates = [r for r in rooms if r.appointments and r.appointments[-1].priority < appt.priority]
        if not candidates:
            return None
        return min(candidates, key=lambda r: (r.appointments[-1].priority, r.id))

def _host(self: Room, appt: Appointment) -> None:
    self.appointments.append(appt)
    self.free_at = appt.end

Room.host = _host

class RoomAllocator:
    def __init__(self, room_count: Optional[int] = None, policy=None):
        self.rooms: list = []
        self.free_ids: list = []
        self.busy: list = []            # (free_at, room_id)
        self.cap = room_count
        self.policy = policy or SmallestIdPolicy()
        self.rejected: list = []
        if room_count is not None:
            for i in range(room_count):
                self.rooms.append(Room(i))
                heapq.heappush(self.free_ids, i)

    def _release(self, now: int) -> None:
        while self.busy and self.busy[0][0] <= now:
            _, rid = heapq.heappop(self.busy)
            heapq.heappush(self.free_ids, rid)

    def assign(self, appt: Appointment) -> Optional[Room]:
        self._release(appt.start)
        if self.free_ids:
            room = self.rooms[self.policy.pick(self.free_ids)]
        elif self.cap is None:
            room = Room(len(self.rooms))
            self.rooms.append(room)
        else:
            victim = self.policy.victim(self.rooms, appt)
            if victim is None:
                self.rejected.append(appt)
                return None
            evicted = victim.appointments.pop()
            victim.free_at = victim.appointments[-1].end if victim.appointments else 0
            self.rejected.append(evicted)
            self.busy = [(t, rid) for t, rid in self.busy if rid != victim.id]
            heapq.heapify(self.busy)
            room = victim
        room.host(appt)
        heapq.heappush(self.busy, (room.free_at, room.id))
        return room

    def assign_all(self, appts: list) -> dict:
        result = {}
        for appt in sorted(appts):                     # dataclass order: (start, end)
            room = self.assign(appt)
            result[appt.id] = room.id if room else None
        for appt in self.rejected:                     # an eviction overrides the earlier answer
            if appt.id in result:
                result[appt.id] = None
        return result

    def busiest(self) -> Room:
        return max(self.rooms, key=lambda r: (len(r.appointments), -r.id))

    def rooms_needed(self) -> int:
        return len(self.rooms)

# phase one: minimum rooms = rooms_needed() after assign_all on an unbounded allocator
if __name__ == "__main__":
    appts = [Appointment(0, 30, "a"), Appointment(5, 10, "b"), Appointment(15, 20, "c"), Appointment(30, 40, "d")]
    alloc = RoomAllocator()
    print(alloc.assign_all(appts), alloc.rooms_needed(), alloc.busiest().id)

Run on the sample, appointment a takes room 0, b needs room 1 (room 0 is busy until 30), c reuses room 1 (free at 10), and d starts exactly at 30 so it takes room 0 back: two rooms with two appointments each, so the busiest tie goes to room 0. Saying those four lines out loud is the whole of phase one and two.

6. Extensions, concurrency and what interviewers probe

• "How many rooms at minimum?" The unbounded allocator's room count after assign_all, which equals the maximum number of overlapping appointments; mention the sweep-line proof.
• "Cap the rooms and evict by priority." Construct with room_count and PriorityEvictionPolicy; the allocator code is unchanged, only the policy answers differently.
• "Appointments arrive out of order." The heap sweep assumes non-decreasing starts; for arbitrary inserts each room keeps a sorted interval list and can_host becomes a bisect, as in meeting room reservation.
• Concurrency: the two heaps change together, so a single lock around assign is required if callers are threads; there is no safe lock-free split.
• Test first: an appointment starting exactly at another's end reuses the room; ties go to the smaller id; the busiest tie goes to the smaller id.
• Common mistake: releasing rooms with < instead of <=, which allocates an extra room for back-to-back appointments and gets the minimum-rooms count wrong.

02Where this question was reported

• ReturnZero · Meeting Rooms phases: min rooms -> assign specific room IDs -> capped capacity with priority eviction
• roundz.substack.com · Assign appointments to rooms by smallest room ID, then return room with most appointments
• LLD Mastery · Commercial tag: meeting room reservation (conflicts, recurring) and list-bookings (filtering, pagination)