Interval Scheduling
Interval scheduling asks how to select the largest set of activities, each with a start and an end time, so that none of the chosen ones overlap. Think of booking the most meetings into one room.
The greedy rule
The winning strategy is surprisingly simple: sort the intervals by their finishing time and repeatedly pick the next interval that starts after the last chosen one ends:
- Sort by end time, earliest first.
- Take the first interval, then scan forward and accept any interval whose start is at or after the current end.
Choosing the earliest finishing activity leaves the most room for everything that follows, which is why this greedy choice is provably optimal.
Related problems
Sorting by start time instead helps merge overlapping intervals or count how many rooms are needed at once. Picking the wrong sort key, such as shortest duration, can produce a worse answer.
Key idea
Always keep the interval that finishes earliest to leave maximum room for later picks.