Meeting room scheduler over a fixed set of rooms

Implement a MeetingScheduler for a fixed set of meeting rooms. Each room has a unique string ID.

• MeetingScheduler(room_ids: list[str]) sets up the rooms. Room IDs are unique.
• schedule(start: int, end: int) -> str | None books a meeting for the half-open interval [start, end) in a room that has no overlapping meeting, and returns that room's ID. If every room is busy at some point in the interval, return None (or raise an error) and book nothing.

Two meetings overlap when they share any moment of time. Because intervals are half-open, a meeting ending at 10 and one starting at 10 do not overlap. When several rooms are free, any one is acceptable, but state your choice; the examples below take the first free room in the order given.

Constraints

• 0 <= start < end <= 10^9
• Up to 100 rooms and up to 10^5 calls to schedule.
• Aim for better than scanning every meeting in every room on each call.

Example 1

s = MeetingScheduler(["north", "south"])
s.schedule(14, 15)  # "north"
s.schedule(14, 16)  # "south"
s.schedule(15, 16)  # "north"  (starts as the first one ends)
s.schedule(15, 17)  # None     (north busy until 16, south busy until 16)

Example 2

s = MeetingScheduler(["x"])
s.schedule(0, 2)   # "x"
s.schedule(4, 6)   # "x"
s.schedule(2, 4)   # "x"   (fills the gap exactly)
s.schedule(1, 5)   # None

Be ready to extend the design: cancelling meetings, room capacities, and picking the room that wastes the least free time.