Greedy Algorithms8 sections · 316 units
Open in Course

Activity Selection - Conclusion

Finishing the proof

By induction, greedy stays ahead at every step. Since greedy's kk-th activity always ends no later than OPT's kk-th activity, greedy can always accommodate at least as many activities as OPT. If OPT has mm activities, greedy can have at least mm activities. Since OPT is optimal, greedy is too.

Two different proofs, same conclusion: earliest-end-first is optimal. You now have two ways to prove the same result. Both approaches confirm that finishing early maximizes your options.