The problem
You have many jobs, each an interval, and one resource that handles one job at a time. Choose the largest set of jobs that never overlap. This is classic interval scheduling.
The greedy choice
Sort jobs by finish time, earliest first. Repeatedly take the next job whose start is at or after the finish of the last job you accepted. This earliest finish first rule is provably optimal.
Why earliest finish wins
Finishing as early as possible leaves the most room for everything after it. An exchange argument shows that if some optimal solution did not start with the earliest finishing job, you could swap that job in without losing any count. Repeating the swap turns any optimal solution into the greedy one.
The walk
- Sort all jobs by finish time.
- Track the finish of the last accepted job, initially negative infinity.
- For each job in order, accept it if its start is not earlier than that finish, then update the finish.
This is one sort plus one linear scan.
Key idea
To pack the most non overlapping jobs, greedily accept the one that finishes earliest among the remaining feasible jobs.