Course contentsShow
← Computer Science
Lesson 907 of 2,87221. Greedy AlgorithmsFree lesson

Proving Activity Selection Correctness

Walk through a complete proof that the earliest-finish-time greedy strategy is optimal.

Proving Activity Selection Correctness

You'll learn: How to rigorously prove that selecting activities by earliest finish time always produces an optimal solution.

The Core Idea

Remember the Activity Selection Problem: given activities with start and finish times, choose the maximum number of non-overlapping activities. The greedy strategy is simple—always pick the activity that finishes earliest. But why does this work?

The proof combines two key ingredients you've seen: the Greedy Choice Property and Optimal Substructure, using an Exchange Argument.

The Proof Walkthrough

Step 1: Assume an optimal solution exists
Let's say some optimal solution O selects activities that give maximum count. Sort all activities by finish time, and let a₁ be the earliest-finishing activity.

Step 2: Show greedy choice is safe
If O already includes a₁, great! If not, O must start with some other activity aₖ that finishes later than a₁. Here's the key: we can exchange aₖ for a₁ in O. Since a₁ finishes earlier, it won't conflict with any activities that came after aₖ. This exchange gives us a solution just as good as O, proving our greedy choice doesn't hurt.

Step 3: Apply optimal substructure
After choosing a₁, we're left with a smaller problem: select from activities starting after a₁ finishes. By the same reasoning, we greedily pick the earliest finisher there, and so on.

Conclusion: Since we can always exchange the first activity in any optimal solution with our greedy choice without losing optimality, and this applies recursively, the greedy algorithm must produce an optimal solution.

Key Takeaway: The Activity Selection greedy algorithm is proven correct through exchange arguments—showing we can safely swap any optimal solution's choices with greedy choices without sacrificing quality.