Meeting Rooms

The Idea

You never need to know which meeting sits in which room — only how many are live at once.

Sort the starts and the ends into two separate lists and sweep. A start claims a room; an end reached before that start frees one. The highest the counter ever reaches is the answer.

Real-World Example

Ward planning in a hospital. Nobody asks which patient lies in bed four; they ask how many beds are occupied at the busiest hour of the night, because that number is what has to be bought.

The Code

meetings = [(0, 30), (5, 10), (15, 20)]
starts = sorted(s for s, _ in meetings)
ends = sorted(e for _, e in meetings)
rooms = peak = j = 0
for s in starts:
    while ends[j] <= s:      # a room freed up before this meeting starts
        rooms -= 1; j += 1
    rooms += 1               # this meeting claims a room
    peak = max(peak, rooms)
print(peak)

starts = [1, 2, 3]
ends = [4, 5, 6]
rooms = peak = j = 0
for s in starts:
  while ends[j] <= s:
      rooms -= 1; j += 1
  rooms += 1
  peak = max(peak, rooms)
print(peak)