Greedy Algorithms8 sections · 316 units
Open in Course

Proof Overview

Why it is optimal

I will prove that earliest-end-first is optimal using exchange argument.

Claim: The greedy solution G has as many activities as any optimal solution OPT. Proof strategy: Take any OPT and show it can be transformed into G without reducing the count. If we can reach G from any OPT, then G is optimal.

The exchange will swap OPT's activity for G's earlier-ending activity without breaking anything. Since finishing earlier never creates conflicts with later activities, the swap is always safe.