From rule to certainty
The activity selection problem is interval scheduling stated as choosing compatible activities. We already know the greedy earliest finish rule works, but a real proof shows two properties that together guarantee optimality.
The greedy choice property
The first property says the greedy choice is safe:
- Let the activity that finishes first be the greedy pick.
- Claim: some optimal solution includes this activity.
- Argument: take any optimal solution and look at its earliest finishing activity. Swap it for the greedy pick. The swap cannot cause an overlap because the greedy pick finishes no later, so the result is still valid and just as large.
This swap is the heart of the exchange argument behind the whole method.
Optimal substructure
The second property is optimal substructure: after committing to the greedy activity, the remaining problem is the same kind of problem on the activities that start after it ends. An optimal solution to that smaller problem, combined with the greedy pick, is optimal overall. Induction on the number of activities then closes the proof, since each step keeps an optimal solution intact.
Key idea
The greedy choice property plus optimal substructure prove activity selection optimal: swap in the earliest finisher, then recurse on what remains.