When the best step now is safe

When is taking whatever looks best at this moment guaranteed to end up best overall?

In life, taking whatever looks best right now is usually a mistake — the whole vocabulary of prudence exists to warn against it. In algorithms, it sometimes gives the provably optimal answer, computed in a single pass, with no backtracking and no search.

So the interesting question is not "is greed good?" — it is neither — but: what property must a problem have for a locally best choice to be guaranteed globally best? And why does that property hold for scheduling meetings and fail for packing a knapsack?

Let us find the property by trying to prove greed correct on a case where it works, and watching what the proof needs.

Interval scheduling: you have a list of meetings with start and end times, one room, and you want to hold as many meetings as possible. The greedy rule is to repeatedly take the meeting that finishes earliest among those still compatible.

Why should that be optimal? Suppose it is not, so some optimal schedule O holds more meetings than greedy does. Take the earliest-finishing meeting overall, call it g, which greedy certainly picks first. Does O contain it? If not, look at O's first meeting and swap it for g. Is the result still a valid schedule? Yes — g finishes no later than the meeting it replaced, so it cannot conflict with anything that came after. And the count is unchanged. So there exists an optimal schedule containing greedy's first choice.

Now notice where that leaves us. After committing to g, what remains is the same kind of problem: schedule as many as possible from the meetings that start after g ends. Repeat the argument on that smaller instance, and by induction greedy matches the optimum all the way down.

Read back over that proof and pull out the two things it actually used. First: there exists an optimal solution containing the greedy choice — the greedy-choice property, established by the swap, which is why this style is called an exchange argument. Second: after making that choice, the leftover is itself an instance of the same problem, and an optimal solution to the whole must contain an optimal solution to the leftover — optimal substructure. Every correct greedy proof has both parts; having only the second is the common failure, since optimal substructure alone gives dynamic programming, not greed.

So test the property rather than the intuition. Coin change: make six units from coins of value one, three and four. Greedy takes the four, then two ones — three coins. But two threes make six in two coins. The exchange argument fails at the first step: no optimal solution contains the four. Optimal substructure still holds perfectly well; the greedy choice property does not. Whether greed works for a coin system depends entirely on the denominations; systems where it does are called canonical, and deciding whether a given set is canonical is itself non-trivial.

The knapsack pair is the cleanest contrast in the subject. In the fractional version you may take part of an item, so the greedy rule of highest value per unit weight is optimal — if a better solution used less of the best item, swap some in, which is exactly the exchange move. In the 0/1 version you cannot take a fraction, the swap is unavailable, and greed can be arbitrarily bad. The same objective, the same ordering, and the difference is only whether the exchange step is legal.

Is there a general characterisation, or only case-by-case proofs? For one important family, yes. If your problem is "choose a maximum-weight set that is independent" and the independence system is a matroid — meaning subsets of independent sets are independent, and any smaller independent set can always be extended from a larger one — then the greedy rule of taking the heaviest admissible element is optimal. The Rado-Edmonds theorem gives the converse too: if greed is optimal for every assignment of weights, the system must be a matroid. That is why Kruskal's algorithm for minimum spanning trees is correct — forests form a matroid — and it is the closest thing to a general answer we have. It does not cover interval scheduling or Dijkstra's method, which have their own arguments.

Two clarifications.

First, "greedy" describes the algorithm, not its quality. A greedy algorithm is any that commits irrevocably to the locally best option; whether that is optimal, approximately optimal, or terrible is a separate question answered by proof. Greedy set cover, for instance, is provably not optimal but always within a factor of about the natural logarithm of the number of elements — and Feige showed in 1998 that no polynomial-time algorithm does asymptotically better unless P equals NP. So greed can be the best available answer while being wrong.

Second, beware of the pattern where greed happens to work on your examples. The counterexamples in this subject are small and unobvious — three coin denominations, two knapsack items — and passing tests is not evidence. What settles it is attempting the exchange argument: take an arbitrary optimal solution, try to transform it into one containing your first greedy choice without making it worse. If that move goes through, you have a proof. If you cannot make it go through, the obstruction you hit is usually the counterexample itself.

• Matroid intersection, where greed stops working but the problem stays tractable by other means.
• The scheduling problems where greed is optimal only after a non-obvious sort, such as minimising total weighted completion time.

Every term the collection defines is gathered in the glossary.