# 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.