Greedy Algorithms8 sections · 316 units
Open in Course

Activity Selection - Base Case

First activity

Base case (k=1k = 1): Greedy picks the activity that ends earliest. By definition, no other solution's first activity ends earlier. So after 11 activity, greedy's end time <= OPT's end time. Greedy stays ahead.

This base case is immediate from the greedy strategy: you pick the earliest-ending activity, so no one can end earlier. The base case establishes that greedy starts in the lead. For stays ahead proofs, most of the reasoning happens in proving the inductive step, not the base.