Greedy on intervals: earliest end first

How many meetings fit in one room at most? The rules that come to mind are wrong: "take the one that starts first" can block the whole day with one long meeting; "take the shortest" can waste two long meetings with a short one that falls right between them. The rule that holds: take the one that ends earliest. A meeting that ends early leaves the most time behind it.

1taken = 0
2free_from = float("-inf")
3for start, end in sorted(meetings, key=lambda m: m[1]):
4    if start >= free_from:
5        taken += 1
6        free_from = end
7return taken

Sort by end; take the first meeting that starts after the room is free (or at that very moment). Note that the sort key is the end: when merging intervals you sorted by start, and here the criterion is a different one.

If the question becomes "all of them must take place; how many rooms are needed?" the idea changes: you no longer drop meetings, you count how many run at the same time. Sort the starts and the ends separately and walk the day from beginning to end: take a room at a start, give one back at an end; the most rooms held at once is the answer.

Tasks