Meeting room scheduler over a fixed set of rooms

Each room keeps its own list of booked meetings. A new meeting [start, end) fits in a room when it overlaps none of that room's meetings. Two half-open intervals [s1, e1) and [s2, e2) overlap exactly when s1 < e2 and s2 < e1, so a meeting that ends at 10 and one that starts at 10 do not clash.

Brute force. For each room in order, scan every booked meeting and check overlap. If a room has no clash, append the meeting and return the room ID. This is O(R · M) per call, where R is the number of rooms and M is the number of meetings in a room. It is correct and is a fine first answer to state out loud.

Better: a sorted list per room. Keep each room's meetings sorted by start time. Meetings in one room never overlap, so sorting by start also sorts them by end. To test a new meeting, binary-search for the first booked meeting whose start is >= start:

• the meeting just before that position (the previous one) must end at or before start, and
• the meeting at that position (the next one) must start at or after end.

Only those two neighbours can clash. Any earlier meeting ends before the previous one does, and any later meeting starts after the next one does. So the fit check is O(log M) per room.

Which room to pick. The reported question only asks for a free room. Make the choice deterministic so tests are stable: try rooms in the order they were given and take the first that fits. Say this choice out loud, because a common follow-up asks for a different policy (best fit, see Follow-ups).

Invariants.

• Each room's list is sorted by start, and no two intervals in it overlap.
• A meeting is stored in exactly one room, and only after the fit check passes. A failed call changes nothing.
• Every interval has start < end; empty or reversed intervals are rejected up front.

from bisect import bisect_left, insort
from typing import Optional


class MeetingScheduler:
    """Books meetings into a fixed set of rooms. Intervals are half-open [start, end)."""

    def __init__(self, room_ids: list[str]) -> None:
        if len(set(room_ids)) != len(room_ids):
            raise ValueError("room IDs must be unique")
        self._order = list(room_ids)
        # room -> sorted list of (start, end); intervals in one room never overlap
        self._bookings: dict[str, list[tuple[int, int]]] = {r: [] for r in room_ids}

    def _fits(self, room: str, start: int, end: int) -> bool:
        meetings = self._bookings[room]
        i = bisect_left(meetings, (start, start))  # first meeting starting at or after `start`
        if i > 0 and meetings[i - 1][1] > start:   # previous meeting runs past our start
            return False
        if i < len(meetings) and meetings[i][0] < end:  # next meeting starts before our end
            return False
        return True

    def schedule(self, start: int, end: int) -> Optional[str]:
        """Book [start, end) in the first room (in the given order) that is free.

        Returns the room ID, or None when every room is busy. A failed call books nothing.
        """
        if start >= end:
            raise ValueError("start must be before end")
        for room in self._order:
            if self._fits(room, start, end):
                insort(self._bookings[room], (start, end))
                return room
        return None

    def meetings(self, room: str) -> list[tuple[int, int]]:
        """The meetings booked in one room, sorted by start."""
        return list(self._bookings[room])


if __name__ == "__main__":
    s = MeetingScheduler(["r1", "r2", "r3"])
    assert s.schedule(9, 10) == "r1"
    assert s.schedule(9, 10) == "r2"
    assert s.schedule(9, 10) == "r3"
    assert s.schedule(9, 10) is None          # all three rooms busy
    assert s.schedule(10, 11) == "r1"         # back-to-back is allowed
    assert s.schedule(8, 9) == "r1"           # fits before r1's 9:00 meeting
    assert s.schedule(8, 12) is None          # clashes everywhere
    assert s.schedule(11, 12) == "r1"
    assert s.meetings("r1") == [(8, 9), (9, 10), (10, 11), (11, 12)]
    assert s.schedule(9, 11) is None
    assert s.schedule(10, 12) == "r2"         # r2 only holds [9, 10)

    gap = MeetingScheduler(["a"])
    assert gap.schedule(1, 3) == "a"
    assert gap.schedule(5, 7) == "a"
    assert gap.schedule(3, 5) == "a"          # exactly fills the gap
    assert gap.schedule(2, 4) is None
    assert gap.schedule(0, 1) == "a"

    assert MeetingScheduler([]).schedule(1, 2) is None
    for bad in [(5, 5), (6, 5)]:
        try:
            MeetingScheduler(["a"]).schedule(*bad)
            raise AssertionError("expected ValueError")
        except ValueError:
            pass
    print("ok")

Let R be the number of rooms and M the largest number of meetings in one room.

• __init__: O(R) time and space.
• schedule: O(R · log M) to find a room, plus O(M) for insort into a Python list (the binary search is log M, the list shift is linear). With a balanced tree or sortedcontainers.SortedList the insert becomes O(log M), so the whole call is O(R · log M).
• meetings(room): O(M) to copy the list.
• Space: O(total meetings booked) across all rooms.

• Rooms ["r1", "r2", "r3"]; schedule(9, 10) three times returns "r1", "r2", "r3"; a fourth time returns None.
• Back-to-back: after [9, 10) in r1, schedule(10, 11) returns "r1" (half-open intervals touch but do not overlap).
• Fits before an existing meeting: schedule(8, 9) returns "r1".
• A long meeting that clashes in every room, schedule(8, 12), returns None and books nothing.
• Exact gap: one room holding [1, 3) and [5, 7); schedule(3, 5) returns that room; schedule(2, 4) then returns None.
• Later room has space when the first does not: schedule(10, 12) skips r1 and returns "r2".
• No rooms: MeetingScheduler([]).schedule(1, 2) returns None.
• Invalid input: schedule(5, 5) and schedule(6, 5) raise ValueError; duplicate room IDs raise ValueError in the constructor.

1. Cancel a meeting. Have schedule return a meeting ID and keep meeting_id -> (room, start, end). To cancel, look up the room, binary-search the interval and delete it: O(log M) to find, O(M) list delete, or O(log M) with a sorted container. Reject unknown or already-cancelled IDs.
2. Room capacity and best fit. Rooms have capacities and meetings have attendee counts. Filter rooms with capacity >= attendees, then pick the one that wastes the least: smallest capacity first, or the room where the meeting leaves the smallest free gap between its neighbours (next.start - prev.end - (end - start)). Both reuse the same two-neighbour check, so each room is still O(log M).
3. Many rooms, many queries. O(R) per call hurts when R is in the thousands. Group rooms by capacity, or keep a per-time-bucket index of free rooms. For "any room is free" questions over a fixed horizon, a segment tree over time slots that stores the minimum number of busy rooms answers in O(log T). State the trade-off: the per-room sorted list is simplest and fine for tens of rooms.
4. Query and print the schedule. meetings(room) already returns sorted intervals. "Which rooms are free during [s, e)?" is the same fit check over all rooms. "How many rooms are needed for this list of meetings?" is Meeting Rooms II: sort starts and ends, or use a min-heap of end times, O(N log N).
5. Concurrency. Two callers must not book the same slot. Use one lock around schedule for the simple version; for scale, lock per room and try rooms in a fixed order, or use an optimistic compare-and-set on a room's version number and retry the next room on conflict. In a database, a unique constraint or an exclusion constraint on (room, time range) does the same job.

Mid-level (L4)

• Gets the overlap test right with half-open intervals, including back-to-back meetings.
• Writes a working brute force, then a sorted-list version with binary search.
• Returns a room ID or a clear failure value, and a failed call leaves state unchanged.

Senior (L5)

• Explains why checking only the two neighbours is enough, and states the invariants.
• Clean class design: input validation, a deterministic room choice, and a way to read back a room's schedule.
• Handles cancel and capacity or best-fit follow-ups without rewriting the core, and gives the correct cost of a Python list insert versus a balanced tree.

Staff (L6+)

• Discusses room-selection policy as a product choice (first fit, best fit, least fragmentation) and its effect on future bookings.
• Covers scale (many rooms, time-bucketed or segment-tree indexes) and concurrency (per-room locks, optimistic retries, database exclusion constraints).
• Raises real-world details: time zones, recurring meetings, and keeping an audit trail of bookings and cancellations.