Card 08/ 08
Recap: Greedy Algorithms
Commit to the best choice, prove it with an exchange, and disprove a wrong rule with one counterexample.
A greedy algorithm takes the choice that looks best at each step and never undoes it, which is fast and correct only when a proof says so. This card gathers what the topic established and where each idea was taught.
| The idea | Where |
|---|---|
| A greedy algorithm commits to the locally best choice; it is right when the problem has the greedy choice property and optimal substructure | Greedy Algorithms: Take the Best Choice Now and Never Revisit It |
| Sorting meetings by end time and keeping each that fits schedules the most, in O(n log n) | Schedule the Most Meetings by Earliest Finish |
| One small counterexample disproves a greedy rule; coins 1, 5, 6 and 9 for 11 take 3 coins greedily against 2 | Trusting a Greedy Rule Without a Proof |
| An exchange argument swaps a best solution's choices for the greedy ones, each swap valid and no worse | Proving a Greedy Choice With an Exchange Argument |
| The sort key is the design decision: earliest deadline first gave worst lateness 1 where shortest first gave 3 | Choosing the Key a Greedy Algorithm Sorts By |
| The greedy algorithm is a sort with a key and one scan; changing the key changes the answer | Greedy Scheduling in Python, Java and TypeScript |
| Value per kilo solves the divisible van and fails the whole one, £22 against £25 | Practice: Loading a Van by Value per Kilo |
Every greedy algorithm in the topic is a sort by one key and a single scan, so each goal comes down to the key below, and each costs the sort.
| Goal | Sort by | Cost |
|---|---|---|
| Most meetings in one room | End time, earliest first | O(n log n) |
| Least total waiting | Duration, shortest first | O(n log n) |
| Smallest worst lateness | Deadline, earliest first | O(n log n) |
| Most value, loads divisible | Value per kilo, highest first | O(n log n) |
Where every greedy key fails, as for whole parcels and arbitrary coins, the problem needs to keep more than one choice alive. Dynamic Programming, the next topic, does that without the exponential cost of backtracking.
← → move through sections and cards