Greedy Pattern

Greedy selects locally optimal steps in the hope of achieving a global optimum. Sometimes this is correct (Huffman, interval scheduling with the right rule), and sometimes it is only a heuristic.

Proof requirement: Matroid or exchange argument, otherwise counterexample.

Where used

Scheduling with deadlines, Huffman-like coding, canonical coin change, activity selection. Fast, but only correct with proof or clear counterexample check.

Depth

A greedy algorithm builds a solution step by step, selecting the next step that is most favorable according to a criterion. Earlier decisions are not re-evaluated during the normal course. However, efficiency alone does not prove that the result is globally optimal.

A correctness proof often uses an exchange argument: An optimal solution can be transformed in such a way that it contains the greedy decision without becoming worse. Alternatively, a greedy-choice property together with optimal substructure shows that the remaining problem retains the same form.

Difficulty levels

1. Name the selection rule and the remaining subproblem.
2. Look for a counterexample for a plausible rule.
3. Formulate an exchange argument for a correct rule.

Pitfalls

An intuitive heuristic is not yet a proof. Especially with weights or constraints, a seemingly favorable decision can restrict later options in such a way that the overall result becomes worse.