Verifying a Greedy Strategy

The idea

A greedy algorithm makes the choice that looks best right now and never reconsiders. Sort the items sensibly, walk through them once, take what you can.

When it works, it is short and fast. The danger is that it is also short and fast when it is wrong — a greedy solution that fails on some inputs looks exactly like one that always succeeds. Verifying the strategy matters more than implementing it.

A case where greedy works

You have coins of value 1, 5, 10, and 25. Make a target amount using as few coins as possible.

Take as many of the largest coin as possible, then the next largest, and so on.

int[] coins = {25, 10, 5, 1};
int remaining = target;
int used = 0;

for (int c : coins) {
    used += remaining / c;
    remaining %= c;
}

System.out.println(used);

This is correct for this specific coin set. It is not correct in general. With coins of 1, 3, and 4, making 6 greedily takes 4 + 1 + 1 = three coins, while 3 + 3 = two coins is better.

A case where greedy is provably right

Given N intervals, select the largest number of them that do not overlap.

Sort by end time, then repeatedly take the first interval that starts after the last one you took.

static class Interval {
    int start, end;
}

Arrays.sort(iv, (x, y) -> Integer.compare(x.end, y.end));

int taken = 0;
int lastEnd = Integer.MIN_VALUE;

for (Interval x : iv) {
    if (x.start >= lastEnd) {
        taken++;
        lastEnd = x.end;
    }
}

System.out.println(taken);

Sorting by end time rather than start time or duration is the entire insight, and it has a clean argument behind it: among all intervals compatible with what you have chosen so far, the one that finishes earliest leaves the most room for everything after it. Choosing it can never make the situation worse, so there is always an optimal solution that starts with that choice.

That form of argument — taking the greedy choice never rules out an optimal answer — is the standard way to justify a greedy algorithm. It is called an exchange argument.

How to check a greedy strategy

Step 3 is the one to actually do. An exchange argument you half-believe is less convincing than ten thousand random tests that agree.

Common greedy shapes

Patterns that recur

The last row has an important caveat. Taking the best value-per-unit ratio is correct when items can be split, and incorrect when they cannot — the indivisible version is the knapsack problem, which needs DP. See Knapsack.

Worked example

N cows each need a stall for the interval [start, end]. Find the minimum number of stalls needed so no two cows share a stall at the same time.

The answer is the maximum number of intervals overlapping at any single moment. Sweep through events rather than reasoning about assignments:

int[] starts = new int[n];
int[] ends = new int[n];
// ... read, then sort each array independently ...
Arrays.sort(starts);
Arrays.sort(ends);

int stalls = 0, most = 0;
int i = 0, j = 0;

while (i < n) {
    if (starts[i] < ends[j]) {
        stalls++;
        most = Math.max(most, stalls);
        i++;
    } else {
        stalls--;
        j++;
    }
}

System.out.println(most);

Sorting the start and end times separately is what makes this work — you no longer care which start goes with which end, only how many intervals are open at once.

Whether the comparison is < or <= decides whether a cow leaving exactly when another arrives can reuse the stall. The problem statement determines that, and getting it backwards is wrong on precisely the inputs where times coincide.

Next