A greedy algorithm builds the solution one piece at a time and, at each step, takes the choice that looks best at that moment, never going back. It is the most natural approach and often the fastest. The problem is that «looks best now» does not mean «leads to the optimum in the end». Sometimes it works perfectly, sometimes it fails spectacularly. Being able to tell the two cases apart is one of the most useful skills in algorithm design.
A case where it works: interval scheduling
A meeting room receives many booking requests, each with a start and an end time. We want to accept the largest number of meetings without overlaps.
Three greedy strategies seem reasonable:
- choose first the meeting that starts earliest;
- choose first the shortest meeting;
- choose first the meeting that ends earliest.
Only the third is always optimal. The first two fail on simple counterexamples: a meeting starting at 8 and ending at 18 defeats strategy 1; a short meeting from 11:30 to 12:30, straddling two meetings 9–12 and 12–15, defeats strategy 2, which accepts one meeting instead of two.
def select(meetings):
chosen, last_end = [], float("-inf")
for start, end in sorted(meetings, key=lambda m: m[1]):
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
The cost is dominated by the sort: n log n.
How to prove a greedy choice is correct
The most common method is the exchange argument. Take any optimal solution and show that it can be modified, without making it worse, until it coincides with the greedy one.
For intervals: let O be an optimal solution and let g be the meeting that ends earliest of all. If O does not contain g, replace the first meeting of O with g. Since g ends no later than it, it creates no overlap with the other meetings in O, and the number of meetings stays the same. So there is an optimal solution containing the greedy choice, and the same reasoning repeats on the rest.
Two properties, together, guarantee success:
- greedy-choice property: there is always an optimal solution that contains the first greedy choice;
- optimal substructure: after that choice, what remains is a smaller problem of the same kind.
Other correct greedy algorithms
- Minimum spanning trees: Kruskal and Prim are greedy; their correctness follows from the cut property.
- Dijkstra: at each step it finalises the nearest vertex; it is greedy, and it works only with non-negative weights.
- Huffman codes: to compress a text, shorter binary codes are assigned to more frequent symbols. The algorithm repeatedly merges the two least frequent symbols (or groups) into a new node. The result is a prefix code of minimum average length, still used inside widespread compression formats today.
- Fractional knapsack: taking items in order of value per unit of weight is optimal, if they can be split.
- Minimising maximum lateness: with jobs that have a duration and a deadline, running them in order of increasing deadline minimises the maximum lateness. Here too the proof is an exchange argument: two consecutive jobs in the wrong order can be swapped without making things worse.
Cases where it fails
| Problem | Greedy choice | Why it fails |
|---|---|---|
| 0/1 knapsack | Highest value per kilo | It can leave capacity unused that another combination would exploit |
| Change with arbitrary denominations | Largest coin | With denominations 1, 3, 4 and change 6 it gives 4 + 1 + 1 instead of 3 + 3 |
| Travelling salesman | Nearest city | The last moves can be extremely long |
| Paths with negative weights | Nearest vertex (Dijkstra) | A later negative edge changes distances already fixed |
The coin case is interesting: with euro denominations the greedy strategy always gives the minimum number of coins, because the system is designed that way. With arbitrary denominations it does not. The same rule can therefore be optimal or wrong depending on the data.
Greedy as a heuristic
Even when it is not optimal, a greedy algorithm is valuable:
- it quickly provides an initial solution to be improved with local search;
- it gives branch and bound an incumbent, increasing pruning;
- for some problems it comes with an approximation guarantee: for set cover, repeatedly choosing the set that covers the most new elements produces a solution at most a logarithmic factor worse than the optimum.
In professional practice the typical path is exactly this: first a simple greedy, to get a result and understand the problem; then a check for an exchange argument; if there is none, a more powerful technique such as dynamic programming or a metaheuristic.
In short
- A greedy algorithm picks the best option of the moment at each step and never goes back.
- In interval scheduling only the «ends earliest» criterion works.
- The exchange argument is the standard way to prove that a greedy choice is optimal.
- MST, Dijkstra, Huffman and the fractional knapsack are correct greedy algorithms; 0/1 knapsack and the travelling salesman are not.
- Even when not optimal, greedy provides initial solutions and sometimes approximation guarantees.
