Greedy Algorithms8 sections · 316 units
Open in Course

Lessons from Activity Selection

Key patterns

What you learned:

1.1. Sort by end time: for maximizing non-overlapping selections.

2.2. Greedy choice property: : Picking the earliest-ending activity never hurts.

3.3. Exchange argument: : Show any OPT can become greedy without losing quality.

4.4. One pass after sorting: : No need for DP or backtracking. You will see this pattern in many interval problems. The core idea: minimize the timeline commitment with each choice. End time determines how much room you leave for future selections.