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.

Sources: Wikipedia: Greedy algorithm

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;
}

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

def min_coins_greedy(coins, amount):
    used = []
    for coin in sorted(coins, reverse=True):
        while amount >= coin:
            amount -= coin
            used.append(coin)
    return used if amount == 0 else None

function minCoinsGreedy(array $coins, int $amount): ?array {
    rsort($coins);
    $used = [];
    foreach ($coins as $coin) {
        while ($amount >= $coin) {
            $amount -= $coin;
            $used[] = $coin;
        }
    }
    return $amount === 0 ? $used : null;
}

    public static List<Integer> minCoinsGreedy(int[] coins, int amount) {
        int[] sorted = coins.clone();
        Arrays.sort(sorted); // ascending, so walk it backwards for the biggest first
        List<Integer> used = new ArrayList<>();
        for (int i = sorted.length - 1; i >= 0; i--) {
            int coin = sorted[i];
            while (amount >= coin) {
                amount -= coin;
                used.add(coin);
            }
        }
        return amount == 0 ? used : null;
    }

    public static List<int> MinCoinsGreedy(int[] coins, int amount) {
        var sorted = (int[]) coins.Clone();
        Array.Sort(sorted);
        Array.Reverse(sorted); // biggest coin first
        var used = new List<int>();
        foreach (int coin in sorted) {
            while (amount >= coin) {
                amount -= coin;
                used.Add(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)?

Use Greedy (exchange argument) when the problem statement says “fewest coins or pieces to make an amount”, “largest that still fits, taken greedily” or “make change with denominations”. A solution built on it usually runs in O(n log n).

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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Greedy (exchange argument) confused with?

Greedy (exchange argument) is most often confused with Dynamic programming (1-D), Backtracking, Sort with a custom comparator and Binary search on the answer.

• 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)?

Interview problems solved with Greedy (exchange argument) include Non-overlapping intervals, Minimum number of arrows, Jump game, Gas station, Task scheduler, Partition labels and Assign cookies.

• 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)?

The target complexity of Greedy (exchange argument) is O(n log n).

O(n log n) when the input has to be sorted first. The pass afterwards is a single loop, O(n).