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.
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
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 it
- 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.