Every office has the same fight: two teams, one room, 10:30 on a Tuesday. The scheduler's job is to say no to one of them instantly and correctly, including for a weekly meeting whose fourth week clashes with something booked last month.
Most calendar and workplace tools have a "find a room" button, and behind it sits the problem this round asks for. The classes are easy to guess. The marks are in three places: an overlap test that is right at the edges (a meeting that ends at 11:00 doesn't clash with one that starts at 11:00), a data structure that answers "is this room free?" without scanning the room's whole history, and a recurring meeting that books all its weeks or none of them.
This lesson builds the scheduler in one process: a sorted interval list per room, a room-selection strategy, recurrence as a value object, invitations with a notifier, and one lock per room.
How the round runs#
"Build a meeting room booking system for our office. Rooms have capacities. People book a room for a time range and invite colleagues; they can also book a weekly meeting. Two meetings must never overlap in the same room. If they don't name a room, pick a sensible one. Working code, 90 minutes."
- 0–10 min — clarify: time granularity, overlap at the edges, room choice, recurrence rules, partial series, invites
- 10–25 min — the classes, the room calendar's interface, the two seams (room selection, notification)
- 25–45 min — the interval structure: conflicts in O(log n), insert, remove
- 45–65 min —
Scheduler.book: validation, room choice, recurrence all-or-nothing, per-room locks - 65–80 min — invitations and cancellation; a demo week and a 30-thread race
- 80–90 min — follow-ups: free-slot search, attendee clashes, many offices
Requirements and clarifying questions#
| You ask | They answer | What it changes |
|---|---|---|
| Does 10:00–11:00 clash with 11:00–12:00? | No, back-to-back is normal. | Half-open intervals: [start, end) |
| Will people always name a room? | Often not; pick one that fits. | A RoomSelector strategy, smallest fit first |
| Recurring meetings? | Daily or weekly, a fixed number of times. | A Recurrence that expands into slots |
| One week of a series clashes? | Reject the series and say which week. | All-or-nothing across the slots, with the clash in the error |
| Invitations? | Attendees get notified and can accept or decline. | An RSVP per attendee; a Notifier |
| How many bookings per room? | A few hundred in the booking window. | A sorted list per room is enough; say what you'd use at more |
When do two meetings overlap?
Meeting A is [s1, e1) and B is [s2, e2). Write the overlap test in one line. Does it treat 10:00–11:00 and 11:00–12:00 as a clash?
One strong answer
They overlap exactly when s1 < e2 and s2 < e1: each starts before the other ends. With half-open intervals, A = 10:00–11:00 and B = 11:00–12:00 give 11:00 < 11:00, which is false, so no clash. Using <= instead would make every back-to-back meeting a conflict, and checking only "does B start inside A?" misses the case where B swallows A whole (B = 9:00–13:00).
The classes#
%% title: Meeting room scheduler: the classes
classDiagram
class Room {
+room_id str
+capacity int
}
class Meeting {
+meeting_id str
+title str
+organizer str
+room_id str
+start datetime
+end datetime
+invites dict
+series_id str
}
class Rsvp {
<<enumeration>>
PENDING
ACCEPTED
DECLINED
}
class Recurrence {
+every timedelta
+count int
+slots(start, end) list
}
class RoomCalendar {
-starts list
-ends list
+conflicts(start, end) list
+add(start, end, meeting_id)
+remove(start, meeting_id)
}
class RoomSelector {
<<interface>>
+candidates(rooms, people) list
}
class Notifier {
<<interface>>
+send(person, message)
}
class Scheduler {
+book(organizer, title, start, end, attendees, room_id, repeat) list
+respond(meeting_id, person, accept)
+cancel(meeting_id, whole_series) int
+is_free(room_id, start, end) bool
}
Scheduler "1" *-- "many" RoomCalendar
Scheduler "1" o-- "many" Meeting
Scheduler --> RoomSelector
Scheduler --> Notifier
Scheduler ..> Recurrence
Meeting --> Rsvp
RoomSelector <|.. SmallestFit
Notifier <|.. OutboxThe RoomCalendar is the heart of it: one per room, holding only that room's bookings, with no idea what a meeting or a person is. Scheduler owns the meetings, the locks and the rules. Keeping the interval logic in its own small class means you can test it with plain datetimes, and replace it with an interval tree later without touching the scheduler.
The interfaces#
Rooms, meetings and recurrence. A Recurrence is a value object: given the first slot, it returns every slot of the series:
# rooms.py, part 1: rooms, meetings, invitations
from __future__ import annotations
import itertools
import threading
from abc import ABC, abstractmethod
from bisect import bisect_left, bisect_right, insort
from dataclasses import dataclass, field
from datetime import datetime, timedelta
from enum import Enum
@dataclass(frozen=True)
class Room:
room_id: str
capacity: int
class Rsvp(Enum):
PENDING = "pending"
ACCEPTED = "accepted"
DECLINED = "declined"
@dataclass
class Meeting:
meeting_id: str
title: str
organizer: str
room_id: str
start: datetime
end: datetime # half-open: [start, end), so 10:00-11:00 and 11:00-12:00 don't clash
invites: dict[str, Rsvp]
series_id: str | None = None
@dataclass(frozen=True)
class Recurrence:
every: timedelta # timedelta(days=7) for weekly
count: int
def slots(self, start: datetime, end: datetime) -> list[tuple[datetime, datetime]]:
return [(start + k * self.every, end + k * self.every) for k in range(self.count)]Finding conflicts: one room's calendar#
The naive check scans every booking in the room: O(n) per request. The trick that makes it O(log n) is an invariant the scheduler already guarantees: bookings in one room never overlap. So if you sort them by start time, they are also sorted by end time, and the bookings that overlap a request [s, e) form one contiguous run:
- every booking at index
< bisect_left(starts, e)starts before the request ends; - every booking at index
>= bisect_right(ends, s)ends after the request starts; - the overlap is the slice between those two indexes, which is the
s1 < e2 and s2 < e1test applied to a whole sorted list at once.
# part 2: one room's calendar: sorted, non-overlapping intervals
class RoomCalendar:
"""Bookings never overlap, so sorted by start they are sorted by end too:
everything overlapping [s, e) is one contiguous run, found with two binary searches."""
def __init__(self) -> None:
self._starts: list[datetime] = []
self._ends: list[datetime] = []
self._ids: list[str] = []
def conflicts(self, start: datetime, end: datetime) -> list[str]:
hi = bisect_left(self._starts, end) # bookings that start before we end
lo = bisect_right(self._ends, start) # bookings that end after we start
return self._ids[lo:hi]
def add(self, start: datetime, end: datetime, meeting_id: str) -> None:
i = bisect_left(self._starts, start)
self._starts.insert(i, start)
self._ends.insert(i, end)
self._ids.insert(i, meeting_id)
def remove(self, start: datetime, meeting_id: str) -> None:
i = bisect_left(self._starts, start)
if i < len(self._ids) and self._ids[i] == meeting_id:
del self._starts[i], self._ends[i], self._ids[i]Finding conflicts is two binary searches; inserting into a Python list is O(n) because elements shift, which for a few hundred bookings per room is microseconds. Say the trade-off out loud: at tens of thousands of bookings per room, use a balanced tree keyed by start, and for calendars where intervals may overlap (a person double-booked in two meetings), the sorted-ends trick breaks and you need a real interval tree, where each node also stores the largest end in its subtree.
The two seams: which room to try, and how to tell people. Smallest fit keeps big rooms free for big meetings:
# part 3: two seams: which room, and who gets told
class RoomSelector(ABC):
@abstractmethod
def candidates(self, rooms: list[Room], people: int) -> list[Room]: ...
class SmallestFit(RoomSelector):
"""Don't put 3 people in the 20-seat boardroom while a 4-seat room is free."""
def candidates(self, rooms: list[Room], people: int) -> list[Room]:
return sorted((r for r in rooms if r.capacity >= people), key=lambda r: (r.capacity, r.room_id))
class Notifier(ABC):
@abstractmethod
def send(self, person: str, message: str) -> None: ...
class Outbox(Notifier): # stands in for email or chat
def __init__(self) -> None:
self.sent: list[tuple[str, str]] = []
self._lock = threading.Lock()
def send(self, person: str, message: str) -> None:
with self._lock:
self.sent.append((person, message))The patterns, and why#
| Pattern | Where | Why it earns its place |
|---|---|---|
| Strategy | RoomSelector / SmallestFit |
"Nearest to the organiser's desk" or "has a video screen" are new selectors, not edits to book(). |
| Observer (light) | Notifier / Outbox |
Email, chat and calendar sync subscribe to booking events; the scheduler only calls send(). |
| Value object | Recurrence |
A rule that expands into slots, immutable and testable on its own. |
| Encapsulated data structure | RoomCalendar |
The sorted lists and the invariant behind them live in one class; swapping in an interval tree touches nothing else. |
Concurrency and edge cases#
The race is the classic one: two requests check that Everest is free at 10:00, both see free, both insert. The fix is to make check and insert one atomic step, and the right granularity is one lock per room. Bookings for different rooms never wait on each other, and a recurring series only ever touches one room, so it takes one lock and checks all four weeks before inserting any of them.
When no room is named, book() tries the candidates in order, taking and releasing each room's lock in turn. It never holds two room locks at once, so there is no lock ordering to get wrong and no deadlock. Notifications are sent after the room lock is released: a slow email server must not hold up everyone booking that room.
- Back-to-back meetings: allowed, because intervals are half-open
- End before start, or zero length: rejected before any lock is taken
- More attendees than seats in the named room: rejected with the room's capacity
- One week of a series clashes: nothing is booked, and the error names the week and the meeting in the way
- The organiser in their own invite list: removed; nobody RSVPs to their own meeting
- Cancelling one occurrence vs the series: one removes a single slot; the other removes every remaining slot with that series id
The code#
The scheduler. Note the shape of book(): pick the rooms to try, then for each one, lock, check every slot, and either move on or insert every slot:
# part 4: the scheduler
class RoomConflict(Exception): ...
class NoRoomFree(Exception): ...
@dataclass
class Scheduler:
rooms: dict[str, Room]
selector: RoomSelector
notifier: Notifier
meetings: dict[str, Meeting] = field(default_factory=dict)
_cal: dict[str, RoomCalendar] = field(default_factory=dict)
_locks: dict[str, threading.Lock] = field(default_factory=dict)
_ids: itertools.count = field(default_factory=lambda: itertools.count(1))
_mu: threading.Lock = field(default_factory=threading.Lock) # guards the meetings dict and ids
def __post_init__(self) -> None:
for rid in self.rooms:
self._cal[rid], self._locks[rid] = RoomCalendar(), threading.Lock()
def book(self, organizer: str, title: str, start: datetime, end: datetime, attendees: list[str],
room_id: str | None = None, repeat: Recurrence | None = None) -> list[Meeting]:
if start >= end:
raise ValueError("a meeting must end after it starts")
people = sorted(set(attendees) - {organizer})
slots = repeat.slots(start, end) if repeat else [(start, end)]
rooms = [self.rooms[room_id]] if room_id else self.selector.candidates(list(self.rooms.values()), len(people) + 1)
for room in rooms:
if room.capacity < len(people) + 1:
raise ValueError(f"{room.room_id} seats {room.capacity}")
with self._locks[room.room_id]: # check every slot, then take every slot: all or nothing
cal = self._cal[room.room_id]
clashes = {f"{s:%a %d %b %H:%M}": ids for s, e in slots if (ids := cal.conflicts(s, e))}
if clashes:
if room_id:
raise RoomConflict(f"{room.room_id} is taken: {clashes}")
continue # this room is busy; try the next one that fits
with self._mu:
series = f"S{next(self._ids):04d}" if repeat else None
made = [Meeting(f"M{next(self._ids):04d}", title, organizer, room.room_id, s, e,
{p: Rsvp.PENDING for p in people}, series) for s, e in slots]
self.meetings.update({m.meeting_id: m for m in made})
for m in made:
cal.add(m.start, m.end, m.meeting_id)
for p in people: # notify after the room lock is released
self.notifier.send(p, f"invite: {title} in {room.room_id}, {start:%a %d %b %H:%M}" + (f" x{len(made)}" if repeat else ""))
return made
raise NoRoomFree(f"no room for {len(people) + 1} at {start:%a %H:%M}")
def is_free(self, room_id: str, start: datetime, end: datetime) -> bool:
with self._locks[room_id]:
return not self._cal[room_id].conflicts(start, end)
def respond(self, meeting_id: str, person: str, accept: bool) -> None:
m = self.meetings[meeting_id]
if person not in m.invites:
raise KeyError(f"{person} isn't invited")
m.invites[person] = Rsvp.ACCEPTED if accept else Rsvp.DECLINED
def cancel(self, meeting_id: str, whole_series: bool = False) -> int:
first = self.meetings[meeting_id]
if whole_series and first.series_id:
targets = [m for m in self.meetings.values() if m.series_id == first.series_id]
else:
targets = [first]
with self._locks[first.room_id]:
for m in targets:
self._cal[m.room_id].remove(m.start, m.meeting_id)
with self._mu:
for m in targets:
del self.meetings[m.meeting_id]
for p in first.invites:
self.notifier.send(p, f"cancelled: {first.title}, {len(targets)} occurrence(s)")
return len(targets)A Monday in the office, a stand-up that has to move rooms, and 30 teams after the same afternoon:
# part 5: a week of meetings, a recurring stand-up, and a race for the boardroom
if __name__ == "__main__":
rooms = {r.room_id: r for r in [Room("Nilgiri", 4), Room("Everest", 8), Room("Himalaya", 20)]}
out = Outbox()
cal = Scheduler(rooms, SmallestFit(), out)
mon = datetime(2026, 11, 2)
at = lambda day, h, m=0: mon + timedelta(days=day, hours=h, minutes=m) # noqa: E731
review = cal.book("asha", "Design review", at(0, 10), at(0, 11), ["ravi", "sana", "imran", "meera"])[0]
print(review.meeting_id, review.room_id, "for 5 people") # Nilgiri seats 4, so Everest
nxt = cal.book("ravi", "Hiring sync", at(0, 11), at(0, 12), ["asha"], room_id="Everest")[0]
print(nxt.meeting_id, "Everest 11:00-12:00 back to back: ok")
try:
cal.book("sana", "1:1", at(0, 10, 30), at(0, 11, 30), ["imran"], room_id="Everest")
except RoomConflict as e:
print("rejected:", e)
cal.book("meera", "Vendor call", at(14, 9), at(14, 10), ["arjun"], room_id="Nilgiri") # Mon 16 Nov
weekly = Recurrence(timedelta(days=7), 4)
try:
cal.book("imran", "Stand-up", at(0, 9, 30), at(0, 9, 45), ["ravi", "sana"], room_id="Nilgiri", repeat=weekly)
except RoomConflict as e:
print("rejected:", e)
standups = cal.book("imran", "Stand-up", at(0, 9, 30), at(0, 9, 45), ["ravi", "sana"], repeat=weekly)
print(len(standups), "stand-ups in", standups[0].room_id, [f"{m.start:%d %b}" for m in standups])
cal.respond(review.meeting_id, "ravi", True)
cal.respond(review.meeting_id, "meera", False)
print({p: r.value for p, r in review.invites.items()})
wins, losses = [], []
def grab(i: int) -> None:
try:
wins.append(cal.book(f"team{i}", "Offsite prep", at(1, 14), at(1, 15), ["x", "y"], room_id="Himalaya"))
except RoomConflict:
losses.append(i)
ts = [threading.Thread(target=grab, args=(i,)) for i in range(30)]
for t in ts:
t.start()
for t in ts:
t.join()
print(len(wins), "booked,", len(losses), "told the room is taken")
print("cancelled", cal.cancel(standups[1].meeting_id), "| then", cal.cancel(standups[0].meeting_id, whole_series=True))
print("Everest Mon 9:30 free again:", cal.is_free("Everest", at(0, 9, 30), at(0, 9, 45)), "| messages sent:", len(out.sent))M0001 Everest for 5 people
M0002 Everest 11:00-12:00 back to back: ok
rejected: Everest is taken: {'Mon 02 Nov 10:30': ['M0001', 'M0002']}
rejected: Nilgiri is taken: {'Mon 16 Nov 09:30': ['M0003']}
4 stand-ups in Everest ['02 Nov', '09 Nov', '16 Nov', '23 Nov']
{'imran': 'pending', 'meera': 'declined', 'ravi': 'accepted', 'sana': 'pending'}
1 booked, 29 told the room is taken
cancelled 1 | then 3
Everest Mon 9:30 free again: True | messages sent: 14The design review has 5 people, so Nilgiri (4 seats) is skipped and Everest is chosen. The hiring sync starts the minute the review ends, and is fine. A 10:30–11:30 request overlaps both, and the error names both. The stand-up series fails in Nilgiri because of the vendor call on 16 November; without a named room the selector tries Nilgiri, finds the same clash, and books all four weeks in Everest. Thirty threads, one booking. Cancelling one stand-up and then the rest of the series frees the slot, and 14 notifications went out along the way.
Extending it: the follow-ups#
- "Find me 30 minutes when all five of us and a room are free." Walk the gaps between bookings in each room's sorted list, intersect them with each person's busy times, return the first gap of 30 minutes. The sorted structure makes gaps cheap to list.
- "Warn when an attendee is double-booked." Keep a per-person calendar of accepted meetings. People can overlap, so this one needs an interval tree (or a scan of the day); flag the clash on the invite instead of refusing it.
- "Book what's free and skip the rest." A
partial=Trueflag: insert the clean weeks, return the clashing ones. Same lock, same check, a different rule for what to do with the result. - "Rooms in three offices and time zones." Store every time in UTC, convert at the edges, and key rooms by office. A weekly meeting is "every Monday at 9:30 local time", so expand recurrence in the office's time zone before converting, or it drifts by an hour at daylight-saving changes.
- "Release rooms nobody shows up to." A check-in deadline 10 minutes after the start; a timer cancels unchecked meetings and frees the slot.
Common mistakes#
- An overlap test with
<=, so back-to-back meetings clash, or one that misses a booking which swallows the request - Scanning every booking ever made for each request instead of a sorted per-room structure
- One global lock, so booking a phone booth waits for the boardroom
- Booking a series week by week, leaving three weeks booked when the fourth fails
- Sending notifications inside the lock
- Storing local times and getting recurring meetings wrong at daylight-saving changes
Meeting room scheduler
Q1/3 Which test is true exactly when [s1, e1) and [s2, e2) overlap?
Answer & explanation
Answer: B
Each must start before the other ends.
<=makes back-to-back meetings clash; "starts inside the first" misses a request that swallows a booking; containment misses partial overlaps like 10:00–11:00 and 10:30–11:30.Q2/3 Why can RoomCalendar find conflicts with two binary searches?
Answer & explanation
Answer: B
Non-overlapping intervals sorted by start are also sorted by end, so the overlapping ones are one contiguous slice. Once intervals can overlap, as in a person's calendar, you need an interval tree.
Q3/3 A weekly stand-up's third week clashes with an existing booking. What does book() do?
Answer & explanation
Answer: C
A series is all-or-nothing by default: check every slot under the room's lock, then insert every slot. Partial booking is a follow-up with its own flag, not an accident of the loop.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.