Expert · Greedy algorithms · 244 of 264
Most meetings
One room, many meetings with start and end times. A meeting can start when the previous one ends. What is the largest number of meetings the room can hold? (Pick the one that ends first, again and again.)
Input: n, then n lines "start end". Output: the largest number of meetings.
Examples
Input
6 1 2 3 4 0 6 5 7 8 9 5 9
Output
4
Input
1 0 10
Output
1
Input
3 1 3 2 4 3 5
Output
2
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.