Expert · Greedy algorithms · 245 of 264
Rooms needed
Given meetings with start and end times, how many rooms are needed so that none overlap? A meeting ending at time t frees its room for one starting at t.
Input: n, then n lines "start end". Output: the number of rooms.
Examples
Input
3 0 30 5 10 15 20
Output
2
Input
2 1 5 5 10
Output
1
Input
4 1 10 2 9 3 8 4 7
Output
4
One more test checks other inputs when you press Check.
Stuck? The idea behind greedy algorithms
Take the best-looking choice at each step and never go back: sorting first usually makes the best choice obvious.
It works only when a local best choice can't spoil the whole answer; for meetings, choosing the one that ends earliest leaves the most room.
meetings = [(1, 4), (3, 5), (0, 6), (5, 7)]
end, count = -1, 0
for s, e in sorted(meetings, key=lambda m: m[1]):
if s >= end:
count += 1
end = e
print(count)Watch for: Sorting by the wrong thing (start instead of end) gives a plausible but wrong answer: try a small case by hand.