Given a schedule of lectures represented as a list of tuples of start and end
[(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, 1)) lecture_events.append((lec, -1)) lecture_events.sort(key=lambda e: (e, e * -1)) active_lectures = 0 required_rooms_n = 0 for event in lecture_events: if event == 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
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.