Interval Scheduling
Maximum set of non-overlapping intervals. Earliest finish first is optimal by an exchange argument.
Intervals and Greedy Choices: Earliest finish first
a is 1-4. It starts at 1, which is after the last kept interval ended (0), so keep it. The next one must start at 4 or later.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(1)
Before this
A variant of
Taught by the same lesson
Intervals and Greedy Choices covers these too, in the same run.