The campus library books study rooms by the hour. Mina books 9–11, Dev books 10–12, and Isha books 11–13. The librarian has two keys. Can she promise everyone a room? Before writing code, decide who holds a key at exactly 11. If Mina hands hers back then, Isha can take it immediately. Two keys suffice.
Build the timetable
Represent each booking as a half-open interval. Its start is included and its end is excluded. At 9 the library needs one room. At 10 it needs two. At 11 a departure and an arrival cancel out. At 12 it drops to one, and at 13 it drops to zero. The answer is the largest occupancy across these stretches.
You can compute this without inspecting every hour or even knowing the time unit. Give each start a change of +1 and each end a change of −1. Combine changes at the same instant before updating the peak.
def rooms_needed(bookings):
changes = {}
for start, end in bookings:
if end <= start:
raise ValueError("A booking must have positive duration")
changes[start] = changes.get(start, 0) + 1
changes[end] = changes.get(end, 0) - 1
active = peak = 0
for instant in sorted(changes):
active += changes[instant]
peak = max(peak, active)
return peak
assert rooms_needed([]) == 0
assert rooms_needed([(9, 11), (10, 12), (11, 13)]) == 2
assert rooms_needed([(9, 11), (11, 13)]) == 1
Change the business rule
Suppose a room needs one hour of cleaning after checkout. The first room is now occupied until 12. Extend each end by one before building the timetable. The same three bookings now require three rooms between 11 and 12. This is a good interview follow-up because the sweep stays the same while the meaning of an event changes.
For n bookings and k distinct event times, the dictionary stores k changes and sorting costs O(k log k). Building the dictionary takes O(n) expected time. The result tells the librarian how many keys to buy. Assigning a particular key to each student would require keeping track of room identities too.
Try drawing a timetable with two different departures and two arrivals at noon. Shuffle the four bookings and check that the peak stays the same. Python sorting reference
