Greedy Algorithms — cheat sheet — Algorithms & Data Structures with Python

A greedy algorithm takes the best-looking choice at each step, never looking ahead and never undoing it; it is correct only on problems that support it.

Core terms

Optimal: the best possible answer by the problem’s measure (most items, fewest coins).
Candidate: one choice available at the current step.
Greedy-choice property: some optimal solution always includes the locally-best choice. Holds at every step means locally-best choices assemble into a globally-best answer.

The shape of every greedy algorithm

A rule to order candidates most-to-least attractive (usually sorting).
A loop walking candidates in that order.
A validity test per candidate: valid means take it and never reconsider; invalid means skip it.

No backtracking, no exploring futures. One pass, one committed choice per step. Fast, but can miss a better global outcome.

Interval scheduling (greedy works)

Problem: pick the most non-conflicting activities, each a (start, end); one at a time.
Rule: take the activity that finishes earliest among the non-conflicting ones. Finishing early leaves the most time for the rest.
Method: sort by end time, track last_end, accept when start >= last_end.

ordered = sorted(activities, key=lambda a: a[1])  # by end
last_end = float("-inf")
for start, end in ordered:
    if start >= last_end:
        chosen.append((start, end)); last_end = end

Exchange argument proves it: greedy’s earliest-finishing pick g finishes no later than any optimal’s first pick o, so g can replace o with no new conflict; the remaining problem is a smaller copy, repeat.

Coin change (greedy fails)

Problem: make an amount with the fewest coins from fixed denominations; rule is “take the largest coin that fits.”
Works on [25, 10, 5, 1] (optimal for every amount), which is the trap.
Fails on [1, 3, 4] for 6: greedy gives 4+1+1 (three coins); best is 3+3 (two). Committing to the 4 blocks the better answer.
Exchange argument breaks: optimal {3,3} contains no 4. General coin systems need dynamic programming.
Takeaway: correctness depends on the exact inputs, not just the problem’s wording.

Complexity (interval scheduling)

Sort by end time: O(n log n); single pass: O(n). Total O(n log n), sort-dominated.
Space: O(n) for the sorted copy and chosen list; as low as O(1) extra if sorted in place.
Greedy coin change is fast; its problem was correctness, never speed.

Gotchas

Assuming greedy works without proof; passing a few examples proves nothing. Prove the greedy-choice property or distrust the answer.
Sorting by the wrong key: interval scheduling needs end time, not start time or shortest duration.
Confusing “greedy is fast” with “greedy is right.” A fast wrong answer is still wrong.
Equality in the conflict test: use start >= last_end, not >, or you reject activities that start exactly when the last ended.
What works on one input set may fail on another (same problem, different data).