Greedy (exchange argument)

How does Greedy (exchange argument) work?

Name the choice made at each step. Usually it is the smallest, largest or earliest option.

Sort the input so that choice is always at the front. That sort is most of the work.

Walk the list once and take whatever still fits. Never look back at a choice already made.

The whole method rests on one claim. Taking the local best never rules out the global best.

Prove it by exchange: take any optimal answer and swap your choice in. If it stays optimal, greedy is safe.

Without that proof greedy fails quietly. It returns a plausible answer that is not the best.

1. sorted by end: [1,3], [2,4], [3,5]Booking meetings. The earliest finish comes first.
2. take [1, 3]It finishes soonest, so it leaves the most room.
3. skip [2, 4]It starts at 2, before the last one ended.
4. take [3, 5]It starts exactly when the room frees up.
5. answer = 2Two meetings fit. Sorting by length instead can lose one.

function minCoinsGreedy(coins, amount) {
    const sorted = [...coins].sort((a, b) => b - a);
    const used = [];
    for (const coin of sorted) {
        while (amount >= coin) {
            amount -= coin;
            used.push(coin);
        }
    }
    return amount === 0 ? used : null;
}

A worked example of Greedy (exchange argument)

Fewest arrows to burst the balloons

Balloons cover horizontal ranges. An arrow shot at x bursts every balloon covering x.

Return the fewest arrows that burst all of them.

Sort the balloons by their right edge.

Shoot at the first right edge and skip every balloon it covers. Then shoot at the next uncovered edge.

function findMinArrowShots(points) {
    points.sort((a, b) => a[1] - b[1]); // by right edge, never by left

    let arrows = 1;
    let shot = points[0][1]; // the earliest right edge

    for (const [start, end] of points) {
        if (start > shot) {
            arrows++;
            shot = end; // this balloon is out of reach of the last arrow
        }
    }

    return arrows;
}

When should you use Greedy (exchange argument)?

These phrases in a problem statement point here:

• •fewest coins or pieces to make an amount
• •largest that still fits, taken greedily
• •make change with denominations
• •prove optimality with an exchange argument

What is Greedy (exchange argument) confused with?

• Dynamic programming (1-D): DP keeps every option open until the end. Greedy commits at once and cannot undo.
• Backtracking: Backtracking tries every choice and keeps the best. Greedy tries one and trusts it.
• Sort with a custom comparator: Most greedy solutions begin with a sort. The comparator is where the choice is written.
• Binary search on the answer: There the feasibility test is often greedy itself. The search only picks the value to test.

Common mistakes with Greedy (exchange argument)

• Skipping the proof

  A greedy rule that sounds right is very often wrong. Hunt for a counterexample first.

• Sorting by the wrong key

  Earliest start and earliest end give different answers. The proof picks the key, not intuition.

• Using it where the choices interact

  Coin change with odd denominations breaks greedy. There DP is the only safe answer.

• Trying to undo a choice

  Once greedy takes something back, it is a search. Write it as backtracking or DP instead.

Which interview problems use Greedy (exchange argument)?

• Non-overlapping intervals: Keep the interval that finishes first.
• Minimum number of arrows: One arrow per group of overlapping ranges.
• Jump game: Track the furthest index still reachable.
• Gas station: Restart at the point where the tank went negative.
• Task scheduler: Place the most frequent task first each round.
• Partition labels: Cut as soon as every letter seen has finished.
• Assign cookies: Give each child the smallest cookie that satisfies them.

What is the time and space complexity of Greedy (exchange argument)?

O(n log n)

Usually O(n log n), dominated by the sort. The pass afterwards is a single loop.