Greedy Algorithms8 sections · 316 units
Open in Course

Proof Step 3 - Conclusion

G is optimal

We showed: any OPT can be transformed into G without losing activities. It means G has at least as many activities as any optimal solution. Since OPT is optimal (by definition), and G >= OPT, G must also be optimal.

The core idea was: swapping to an earlier-ending activity never causes conflicts with later activities. The greedy choice is always safe. This completes the proof. Greedy is optimal. The core idea: ending earlier strictly improves or maintains your future options.