Greedy Algorithms8 sections · 316 units
Open in Course

Example - Activity Selection Stays Ahead

Alternative proof

Let me prove activity selection with stays ahead instead of exchange.

Measure of progress: After selecting kk activities, the end time of the kk-th activity. Claim: After greedy selects kk activities, its kk-th activity ends no later than any optimal solution's kk-th activity.

If this is true, greedy can always fit at least as many future activities as OPT. So greedy gets at least as many total activities. The earlier you finish, the more room you have for future choices.