Algorithms / Interval Scheduling Greedy
Least You Need to Know: Interval Scheduling and Earliest-Finish Greedy
For maximizing how many non-overlapping intervals you can keep, the standard greedy rule is to sort by **earliest finishing time** and repeatedly accept the next compatible interval. The reason is that earlier finishes preserve more room for future choices.
The least you need to know
- Interval scheduling asks for the maximum number of mutually non-overlapping intervals.
- Sorting by finish time is the classic safe greedy ordering for the count-maximization version.
- After selecting one interval, only intervals starting at or after the current end remain feasible.
- Sorting by start time or shortest duration can fail for the maximize-count goal.
- Closely related interval problems may need different tools, such as heaps for room allocation.
Key notation
[s, f)
interval with start s and finish f
current_end
finish time of last accepted interval
compatible
new interval starts after or at current_end
Tiny worked example
- Sort intervals by finishing time.
- Accept the first interval.
- Track the finish time of the last accepted interval.
- Scan left to right and accept the next interval whose start is at least that finish time.
Common mistakes
- Students often sort by start time because it feels natural, but that rule can leave less room later.
- Students often forget to compare a candidate interval against the finish time of the last accepted interval.
- Students often reuse earliest-finish greedy for a different objective such as minimum meeting rooms, which is a different problem.
How to recognize this kind of problem
- The prompt asks for the largest subset of non-overlapping meetings or jobs.
- Intervals are independent choices with pairwise compatibility conditions.
- Choosing one interval should leave as much remaining time as possible.
Next recommended lesson
Continue through this topic with Least You Need to Know: Invariants and Structural Induction.
Least You Need to Know: Invariants and Structural InductionRelated lessons
Keep going with nearby lessons in the same topic.