Know this before you start: “Why the locally best choice is safe here”

When the locally best choice is safe

Greedy is correct when taking the best-looking option now can never block a better final answer. Argue it, or find a counterexample, before coding.

The idea

A greedy algorithm commits to the best-looking move and never looks back. It's fast and short, but often wrong.

It's safe when an exchange argument holds: any optimal answer can be changed to include the greedy choice without getting worse. For “most meetings”, the meeting that ends first leaves the most room, so swapping it in never hurts.

If you can't argue that, test small cases. One counterexample means you need DP or search.

See it step by step

Coins [1, 3, 4], make 6

Greedy takes the biggest coin first: 4, then 1, then 1 → 3 coins.
But 3 + 3 = 6 uses 2 coins.
Greedy fails here, so this needs DP. With US coins (1, 5, 10, 25) greedy happens to work.

In code (Python)

def greedy_coins(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else -1

def dp_coins(coins, amount):
    best = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                best[a] = min(best[a], best[a - c] + 1)
    return best[amount]

print(greedy_coins([1, 3, 4], 6), dp_coins([1, 3, 4], 6))   # 3 2
print(greedy_coins([1, 5, 10, 25], 30))                     # 2

Greedy: usually O(n log n). The DP fallback is slower but always right.

When you'll use it

Before committing to any greedy solution: jump game, gas station, intervals, scheduling.

Common mistakes

Trusting greedy because it passed the examples.
Giving up on greedy too early when a simple exchange argument exists.