Minimum required lecture rooms scheduling in Python
Given a schedule of lectures represented as a list of tuples of start and end
times like [(15, 16), (13, 15), (14, 15)], return the minimum number of
lecture rooms required to run all of the lectures.
We can solve this in $O(n\log_2n)$, due to the need to sort the lecture times.
The overall steps are:
- Convert time tuples into “lecture event” tuples of time and type, i.e. start or end.
- Sort the lecture events by time and then type.
- Iterate lecture events, tracking current active lectures.
- Track the max active lectures.
A Python implementation looks like this:
def lecture_rooms(lectures: List[Tuple[int, int]]) -> int:
lecture_events = []
for lec in lectures:
lecture_events.append((lec[0], 1))
lecture_events.append((lec[1], -1))
lecture_events.sort(key=lambda e: (e[0], e[1] * -1))
active_lectures = 0
required_rooms_n = 0
for event in lecture_events:
if event[1] == 1:
active_lectures += 1
else:
active_lectures -= 1
required_rooms_n = max(required_rooms_n, active_lectures)
return required_rooms_n
We convert each lecture time tuple such as (15, 16) into two separate events,
which in this example would be (15, 1) and (16, -1). The second part of
each event tuple represents whether this is a lecture start event or a lecture
end event.
We then sort the list of lecture event tuples by both their time and the type of
the event (note the need for * -1 to sort with the start events first and the
end events second).
The sorted list of events looks like this:
[(13, 1), (14, 1), (15, 1), (15, -1), (15, -1), (16, -1)]
Then we iterate the sorted lecture events, incrementing and decrementing a count of “active lectures” based on the type of each event. We track the max of this count and return it at the end.