Greedy algorithms

A greedy algorithm makes an irrevocable locally preferred choice at each step. It is correct only when the problem has structure proving that some optimal solution begins with that choice.

Greedy is a proof obligation, not a performance shortcut.

Design process

1. Define the candidate choices and feasibility constraints.
2. State the local selection rule precisely.
3. Show the choice leaves a smaller problem of the same form.
4. Prove the choice can belong to an optimal solution.
5. Determine the data structure needed to select choices efficiently.

Sorting often dominates runtime, so a greedy scan is commonly \(O(n\log n)\) overall rather than \(O(n)\).

Proof techniques

Exchange argument

Take an optimal solution that does not make the greedy choice. Show its first conflicting choice can be exchanged for the greedy choice without losing feasibility or value. Repeating the exchange transforms an optimum into one consistent with the algorithm.

Stays-ahead argument

Show that after every step, the greedy partial solution is at least as good as any competing partial solution under a useful measure.

Cut or structural property

Show that the lightest, earliest, or otherwise preferred choice crossing a defined boundary is safe. Minimum-spanning-tree proofs use cut properties.

An example is not a proof. Test data can disprove a greedy rule but cannot establish it for every input.

Interval scheduling

Problem: select the maximum number of non-overlapping intervals.

Greedy rule: repeatedly select the compatible interval with earliest finish time.

Why it is safe: if an optimal solution starts with another interval, replacing that first interval with the earliest-finishing compatible one cannot reduce room for later intervals. The remaining problem has the same form.

After sorting by finish time, scan once:

• time: \(O(n\log n)\);
• extra space: depends on sorting and output storage.

Changing the objective—such as maximizing total interval weight—invalidates this rule and leads to a different problem, commonly dynamic programming.

Fractional versus 0/1 knapsack

For fractional knapsack, items may be divided. Selecting by decreasing value-to-weight ratio is optimal because any lower-ratio portion can be exchanged for a higher-ratio portion.

For 0/1 knapsack, items are indivisible. The same greedy rule is not generally correct; use dynamic programming, search, approximation, or a solver based on constraints.

Huffman coding

Huffman coding repeatedly combines the two least-frequent symbols or subtrees using a min-heap. The result is an optimal prefix code under the model's symbol-frequency assumptions.

• heap construction and repeated combination: \(O(n\log n)\) in a straightforward implementation;
• output depends on frequency and tie handling;
• the encoded stream also needs a way to communicate or reconstruct the code tree.

Use standard compression libraries in production. The algorithm is useful for studying greedy exchange structure and prefix codes.

Graph examples

• Kruskal and Prim are greedy minimum-spanning-tree algorithms justified by cut properties.
• Dijkstra greedily settles a minimum tentative distance only when edge weights are non-negative.
• Greedy best-first search is not generally a shortest-path algorithm.

A small change in assumptions can invalidate the proof.

A counterexample habit

Before trusting a greedy rule, search for small counterexamples.

With coin denominations {1, 3, 4} and target 6, repeatedly taking the largest coin gives 4 + 1 + 1, while 3 + 3 uses fewer coins. The rule works for some denomination systems, not all.

Useful adversarial patterns include:

• one locally attractive choice blocking two slightly smaller choices;
• ties whose order changes the result;
• a large ratio but poor total fit;
• negative or zero values outside the proof assumptions.

Greedy versus dynamic programming

Question	Greedy	Dynamic programming
Reconsiders choices?	no	combines stored subproblem results
Correctness basis	greedy-choice property and optimal substructure	recurrence over all relevant choices
Typical memory	low beyond ordering structure	proportional to state space
Main risk	plausible local rule is globally wrong	state explosion or wrong recurrence/order

Use greedy when its proof holds. Use DP when multiple choices must remain represented to guarantee the result.

Tests and checks

Test empty input, ties, already ordered and reverse input, incompatible candidates, negative/zero values where allowed, and known counterexamples to tempting alternative rules.

For small instances, compare with exhaustive search or a trusted solver. Validate feasibility separately from optimal value.