Why it matters

Greedy is often the fastest algorithm when it works. Recognizing when it applies avoids over-engineering with DP or search.

Advertisement

The architecture

A greedy algorithm: at each step, choose the option that looks best locally, commit to it, don't reconsider.

Correctness proofs: exchange argument (show any solution can be transformed to greedy without loss), or optimal substructure (subproblem after greedy choice has same structure).

Greedy strategy patternLocal choicebest option nowCommitno backtrackingVerify optimalityexchange argumentWorks when local optima lead to global; fails when they don't (0/1 knapsack)
Greedy pattern.
Advertisement

How it works end to end

Activity selection: sort by end time, greedily pick non-overlapping activities. Correct because earliest-end-time never hurts.

Huffman coding: greedily merge two lowest-frequency symbols. Produces optimal prefix code.

Dijkstra: always relax edges from the closest unvisited node. Correct with non-negative weights.

Interval scheduling and interval partitioning have variants with different greedy heuristics.