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:

1. Convert time tuples into “lecture event” tuples of time and type, i.e. start or end.
2. Sort the lecture events by time and then type.
3. Iterate lecture events, tracking current active lectures.
4. 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.