A greedy algorithm takes the best move available right now and never reconsiders. It is the simplest thing you can write, and for most problems it is simply wrong.
What makes the technique worth learning is the small set of problems where it is provably right, and knowing how to tell them apart.
Where it fails#
Making change for 30 using coins of 25, 10 and 1. Greedy takes the 25, then needs five 1s: six coins. The right answer is three 10s.
Greedy fails here because taking the 25 changes what is left in a way that cannot be undone. The move that looks best now closes off the better route.
Where it works#
Now make change for 30 with coins of 1, 5, 10 and 25, the everyday set. Greedy gives 25 + 5, and no answer is shorter. Same algorithm, different coins, different outcome.
So the algorithm is not what makes it correct. The structure of the problem is.
The question to ask#
Does taking the best move now ever stop me reaching the best answer overall?
If you can argue it does not, greedy is right. If you cannot, it is not, and the usual alternative is dynamic programming, which tries a move and keeps the answer for everything it leads to.
The argument usually takes this shape: whatever the best possible answer is, I can change it to use my greedy move without making it worse. If that holds, your move is at least as good as any other, so taking it is safe.
Intervals, where greedy really does work#
A great many greedy problems are about intervals, meaning pairs like [start, end]. Meeting times, bookings, ranges on a number line.
The first move is nearly always the same: sort them. Which end you sort by is the whole problem.
Sort by start when you are combining overlapping ranges. Once sorted by start, anything that overlaps a range is adjacent to it, so one pass merges everything:
[1,3] [2,6] [8,10] [15,18] sorted by start
[1,6] [8,10] [15,18] the first two overlap and become one
Sort by end when you are keeping as many non-overlapping ranges as possible. Always keep the one that finishes earliest, because finishing early leaves the most room for everything after it. That is the exchange argument in one sentence, and it is why sorting by start gives the wrong answer here: a range that starts early can run very long and block several short ones.
Overlap, written once#
Two intervals a and b, with a starting no later than b, overlap when:
a.end >= b.start
Whether >= or > is right depends on whether touching counts as overlapping. [1,2] and [2,3] either share the single point 2 or they do not, and the problem has to tell you. Getting this wrong is the commonest interval bug, and it is invisible until a test case touches exactly.
The cost#
Sorting dominates: O(n log n). The pass afterwards is O(n). Memory is O(1) beyond the sort and the answer.
That is worth noticing, because greedy is often chosen over dynamic programming exactly to avoid a quadratic table.
Common mistakes#
- Assuming greedy works because it passed the examples. The examples are where greedy looks best.
- Sorting by the wrong end. Merging wants starts, choosing wants ends.
- Getting the touching case wrong, and never testing an interval that touches exactly.
- Comparing against the original interval after merging, instead of against the merged one, which has a later end.