When greedy works (exchange argument)

A greedy algorithm builds the answer one decision at a time, always taking the option that looks best right now (the smallest, the earliest, the cheapest) and never undoing it. There is no backtracking and no table of subproblems, so greedy solutions are usually short and fast, often O(n log n) because of one sort.

The catch is that 'looks best now' is not always best overall. Greedy is correct only for problems with two properties: the greedy-choice property (some optimal solution starts with the greedy choice) and optimal substructure (after making that choice, what is left is a smaller instance of the same problem).

The standard way to prove the greedy-choice property is the exchange argument: take any optimal solution, swap one of its choices for the greedy choice, and show the result is still valid and no worse. If that swap always works, greedy is optimal.

1. 1Find the decision you make repeatedly: which item to take next, which interval to keep, which child gets the next cookie.
2. 2Propose a rule for that decision, usually 'sort by some key and take the first that fits'. Typical keys are smallest size, earliest end time, largest ratio, or farthest reach.
3. 3Try to break the rule with small counterexamples (2 to 4 items). If you find one, the rule is wrong; try another key or switch to DP.
4. 4Prove it with an exchange argument: take an optimal solution that differs from greedy at the first step, swap in the greedy choice, and show it is still feasible and not worse. By induction, greedy matches an optimal answer at every step.
5. 5Implement: sort (O(n log n)) or use a heap, then one linear pass that keeps a little state (count, last end, current reach).

def find_content_children(greed, cookies):
    """Assign cookies: each child i needs a cookie >= greed[i]."""
    greed.sort()
    cookies.sort()
    child = 0
    for size in cookies:              # smallest cookie first
        if child < len(greed) and size >= greed[child]:
            child += 1                # least greedy child takes it
    return child


def greedy_coins(coins, amount):
    """Largest-coin-first change. Optimal only for canonical systems."""
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else -1

# find_content_children([1, 2, 3], [1, 1])  -> 1
# greedy_coins([1, 5, 10, 25], 63)          -> 6 (optimal)
# greedy_coins([1, 3, 4], 6)                -> 3, but 3 + 3 uses 2 coins

find_content_children is a correct greedy proved by the exchange argument, O(n log n) for the sorts. greedy_coins shows the same style of rule failing on a non-canonical coin set, which is why general coin change is solved with DP.

Cost: Usually O(n log n) for the sort plus O(n) for the pass, with O(1) extra space beyond the sort; heap-based greedy is O(n log n).