Design the booking logic for a set of meeting rooms. Times are non-negative integers.
Bookings are written [start, end). A room is busy from start up to, but not during, end. So [60, 90) and [90, 120) sit back to back with no clash, and one room can hold both. Two bookings clash only when each one begins before the other finishes.
Any booking with start >= end is invalid: the method raises ValueError.
Implement MeetingRoom for a single room.
MeetingRoom() starts empty.book(start, end) -> bool: if [start, end) overlaps no existing booking, store it and return True. Otherwise store nothing and return False.ValueError if start >= end.cal = MeetingRoom()
cal.book(60, 90) # True
cal.book(90, 120) # True (touches, does not overlap)
cal.book(80, 95) # False
<= instead of < in the overlap test, which rejects touching bookings like [60, 90) and [90, 120).after but is still running.True True True
cal = MeetingRoom() print(cal.book(60, 90)) print(cal.book(90, 120)) print(cal.book(30, 60))
Book meetings into one room without overlaps, assign the lowest-numbered free room and count how many rooms a schedule needs, add cancellation and an earliest-free-slot search, then report the busiest periods.
Also known as: Meeting Rooms, Minimum meeting rooms, Merge intervals (related)
Intervals and sweep lines shows up in 6.5% of the 1,447 coding interview reports we studied, at 10 companies. Merge, split or count overlapping ranges of time or numbers.
Reported at: Rippling, Amazon, OpenAI, Scale AI, Databricks, Citadel, Roblox, Waymo, Snowflake, Robinhood.
This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.
Follow-ups candidates reported on questions with this pattern, in our words. Parts marked “from reports” below are built on them.
Design the booking logic for a set of meeting rooms. Times are non-negative integers.
Bookings are written [start, end). A room is busy from start up to, but not during, end. So [60, 90) and [90, 120) sit back to back with no clash, and one room can hold both. Two bookings clash only when each one begins before the other finishes.
Any booking with start >= end is invalid: the method raises ValueError.
Implement MeetingRoom for a single room.
MeetingRoom() starts empty.book(start, end) -> bool: if [start, end) overlaps no existing booking, store it and return True. Otherwise store nothing and return False.ValueError if start >= end.cal = MeetingRoom()
cal.book(60, 90) # True
cal.book(90, 120) # True (touches, does not overlap)
cal.book(80, 95) # False
Now there are several rooms.
BookingSystem(n_rooms): rooms are numbered 0 to n_rooms - 1 and start empty.BookingSystem.book(start, end) -> int: book [start, end) in the lowest-numbered room that is free for the whole interval and return that room's number. Return -1 if no room is free (nothing is stored). Raise ValueError if start >= end.min_rooms(intervals) -> int: a separate function. Given a list of (start, end) tuples, return the fewest rooms needed to hold all of them at once. Touching intervals can share a room. An empty list needs 0.b = BookingSystem(2)
b.book(0, 30) # 0
b.book(10, 20) # 1
b.book(15, 25) # -1
b.book(30, 40) # 0
min_rooms([(0, 30), (5, 10), (15, 20)]) # 2
Add two methods to BookingSystem.
cancel(room, start) -> bool: remove the booking in room that starts exactly at start and return True. Return False if there is no such booking or the room number does not exist. A cancelled slot can be booked again.earliest_free_slot(after, length) -> tuple[int, int]: return (start, room) for the earliest start >= after such that [start, start + length) overlaps no booking in room. If several rooms allow the same earliest start, return the lowest room number. It only searches; it books nothing. Every room is free after its last booking, so an answer always exists when there is at least one room. Raise ValueError if length <= 0.b = BookingSystem(2)
b.book(0, 30); b.book(0, 10); b.book(20, 50) # rooms 0, 1, 1
b.earliest_free_slot(0, 10) # (10, 1) room 1 is free from 10 to 20
b.earliest_free_slot(0, 15) # (30, 0)
b.cancel(0, 0) # True
b.earliest_free_slot(0, 15) # (0, 0)
Write peak_periods(intervals) -> tuple[int, list[tuple[int, int]]], a separate function over a list of half-open (start, end) intervals with start < end.
(start, end) tuples sorted by start. Make each range as long as possible: two peak ranges that touch, like (2, 5) and (5, 6), are reported as one (2, 6).t and another starting at t are never both counted at t.(0, []).peak_periods([(0, 30), (5, 10), (15, 20)]) # (2, [(5, 10), (15, 20)])
peak_periods([(1, 5), (5, 8), (2, 6)]) # (2, [(2, 6)])
Open this page on a laptop or desktop to write and run your code against the tests in the browser.
Spoilers: try each part before reading its walkthrough.
Keep the room's bookings sorted by start time in two parallel lists, starts and ends. Since bookings never overlap, sorting by start also sorts them by end. A new interval can only clash with its two neighbours in that order, so there is no need to scan everything. bisect_right(starts, start) gives the insertion point i. The booking at i - 1 clashes if it ends after the new start; the booking at i clashes if it starts before the new end. Strict comparisons are what make half-open intervals work: a booking ending at 90 and one starting at 90 do not clash. The check is O(log n). Inserting into a Python list is O(n) because of shifting, which a balanced tree or sorted container would bring down to O(log n).
For BookingSystem.book, reuse one MeetingRoom per room and try them in number order; the first that accepts wins, which gives the lowest free room in O(R log n). min_rooms is the classic sweep. Sort intervals by start and keep a min-heap of end times, one per room currently in use. For each interval, if the smallest end is at or before its start, that room is free again, so replace that end with the new one using heapreplace. Otherwise push a new end and the room count grows. Once every interval is placed, len(ends) is the room count. Using <= rather than < is the half-open rule again. Sorting dominates, so it runs in O(m log m) time with O(m) heap space.
cancel finds the booking by its exact start with bisect_left and deletes it from both lists, returning False for a missing start or an out-of-range room. earliest_free_slot looks at each room separately. Begin at t = after. If a booking is running at t, jump t to its end. Then, while the next booking starts before t + length, the gap is too short, so move t to that booking's end and continue. When the loop stops, [t, t + length) is free: either a gap was long enough or the room has no later bookings. Take the smallest (t, room) across rooms, which also breaks ties toward the lower room number. Each room costs O(log n) to locate plus the bookings it walks past.
A sweep line answers both questions at once. Keep a dict from time to net change: an interval adds one where it begins and removes one where it finishes. Several changes landing on the same moment therefore cancel before anything is measured; this is the half-open rule in action, because a hand-over at minute 5 nets to zero. Walk the distinct times in sorted order, adding each net change to a running level. Between one time and the next the level cannot change, so that gap is a range with a known count. When the level beats the best so far, restart the list with this gap; when it ties, either extend the last range (if it ends where this one starts) or add a new one. Sorting the change points dominates, O(m log m).
Keep the room's bookings sorted by start. A new booking can only clash with its neighbours: the booking just before it (does it end after the new start?) and the one just after (does it start before the new end?). bisect finds that position.
For min_rooms, walk the intervals in start order while a heap holds the finishing time of every occupied room. When the smallest end time is no later than the next start, reuse that room instead of opening a new one.
For earliest_free_slot in one room, begin at after, jump past any booking running at that moment, then walk the later bookings in order while the next one starts before your candidate slot ends. Take the earliest result across rooms.
Give each interval a plus-one where it opens and a minus-one where it closes, total those per time, and walk the times in order. Between two consecutive times the count is constant, so each gap is one candidate range.
<= instead of < in the overlap test, which rejects touching bookings like [60, 90) and [90, 120).after but is still running.MeetingRoom.book finds its position with binary search in O(log n) and inserts into a Python list in O(n) for n bookings; a balanced tree or sorted container would make both O(log n). min_rooms is O(m log m) for m intervals. BookingSystem.book tries rooms in order, O(R x n) worst case for R rooms. cancel is O(n) (list delete). earliest_free_slot walks each room's bookings from the binary-search point, O(R x n) in the worst case. peak_periods sorts the distinct change points, O(m log m) for m intervals, and then makes one pass.
The company guides collect the questions candidates report, with every part, the follow-ups interviewers added, and how often each one comes up.
Browse the interview guides