Fitting the most jobs
Suppose many jobs each occupy a time interval and you control one machine that runs one job at a time. Interval scheduling maximization asks for the largest set of jobs you can run without any two overlapping. A greedy rule solves it cleanly.
The earliest finish rule
The winning strategy is surprisingly simple:
- Sort the jobs by their finishing time, earliest first.
- Walk the sorted list and take a job whenever it starts after the last taken job ends.
- Skip any job that would overlap a job already chosen.
Choosing the job that frees the machine soonest leaves the most room for the jobs that follow, which is the intuition behind why this works.
Why greedy is safe here
Sorting by start time or by shortest duration can fail, but earliest finish never does. The proof rests on an exchange argument: any optimal schedule can be transformed step by step into the greedy one without losing any jobs, because swapping in the earliest finishing choice never blocks a later selection. After sorting, a single pass produces an optimal answer.
Key idea
Sorting by earliest finishing time and greedily taking compatible jobs yields the maximum set of non overlapping intervals.