Introduction

You cannot tell that a problem is optimally solvable by a greedy algorithm just by seeing that a greedy choice “feels reasonable.” A greedy solution is correct only when the problem has the right structure, usually described as the greedy-choice property together with optimal substructure.

What a Greedy Algorithm Assumes

A greedy algorithm makes the best-looking local choice at each step and never revisits it. That works only when each local choice can be extended into some globally optimal solution.

In practice, you are usually looking for evidence like this:

• after making the greedy choice, the remaining subproblem is still of the same kind
• an exchange argument shows any optimal solution can be transformed to begin with the greedy choice
• there is no future dependency that makes an early local win become a later loss

If you cannot justify something like that, greediness is a guess, not a proof.

A Classic Problem Where Greedy Works

Interval scheduling is a standard example. If the goal is to select the maximum number of non-overlapping intervals, choosing the interval that finishes earliest is optimal.

Here is a Python implementation:

1def max_non_overlapping(intervals):
2    intervals = sorted(intervals, key=lambda x: x[1])
3    result = []
4    current_end = None
5
6    for start, end in intervals:
7        if current_end is None or start >= current_end:
8            result.append((start, end))
9            current_end = end
10
11    return result
12
13
14data = [(1, 3), (2, 5), (4, 6), (6, 8), (5, 7)]
15print(max_non_overlapping(data))

The proof idea is an exchange argument: if an optimal solution starts with an interval that finishes later than the earliest-finishing interval, you can swap them without reducing the number of intervals you can still schedule afterward.

That is the kind of reasoning that makes a greedy algorithm trustworthy.

A Problem Where Greedy Fails

Coin change is the classic warning. If the coin system is 1, 3, 4 and you want amount 6, the greedy strategy picks 4, then 1, then 1, using three coins. But the optimal solution is 3 + 3, which uses two.

1def greedy_coin_change(amount, coins):
2    coins = sorted(coins, reverse=True)
3    used = []
4
5    for coin in coins:
6        while amount >= coin:
7            used.append(coin)
8            amount -= coin
9
10    return used
11
12
13print(greedy_coin_change(6, [1, 3, 4]))

This is why “locally largest” is not a proof. Some coin systems support greedy change, but not all of them.

How to Test the Idea Before Trusting It

A practical checklist is:

1. Write the natural greedy rule clearly.
2. Try to prove an exchange argument.
3. Look for a small counterexample.
4. Compare with dynamic programming or brute force on small inputs.

If brute force on small cases quickly finds counterexamples, the greedy idea is not universally optimal.

This comparison pattern is especially useful in interviews and contests. Even if you suspect greediness, verifying it on small enumerated cases can save you from committing to the wrong strategy.

Greedy Versus Dynamic Programming

Greedy algorithms are attractive because they are often simpler and faster. But when future choices depend strongly on current decisions, dynamic programming is usually safer because it explores and stores multiple subproblem states instead of committing too early.

A rough rule:

• use greedy when you can prove local choices never block global optimality
• use dynamic programming when the best next move depends on unresolved future tradeoffs

That is not a theorem by itself, but it is a good design instinct.

Common Pitfalls

The biggest mistake is proving that a greedy choice is locally best and then stopping there. Local desirability is not enough.

Another issue is testing only a few happy-path examples. Many bad greedy algorithms look correct on small or friendly inputs and fail only on carefully chosen counterexamples.

Developers also sometimes confuse “produces a good answer quickly” with “is always optimal.” Heuristics can be useful, but they are different from provably optimal greedy algorithms.

Finally, do not force a greedy proof after the fact. If the exchange argument does not come together cleanly, that usually means you need a different algorithmic approach.

Summary

• A greedy algorithm is optimal only when the problem has the right structure.
• The usual proof tools are the greedy-choice property, optimal substructure, and an exchange argument.
• Interval scheduling is a standard case where greedy works.
• Coin change in arbitrary denominations is a standard case where greedy can fail.
• If you cannot prove the greedy rule, validate against counterexamples or use a stronger method such as dynamic programming.