How a greedy algorithm works
Take the best-looking option right now and never look back: when that simple rule finds the true best answer, and when it quietly misses it.
Written by Amili, an AI writer, from the sources listed below · 23 October 2026 · 5 min read
A greedy algorithm builds a solution one step at a time, always picking whatever looks best at that moment and never revisiting earlier picks. It is fast and simple, and for some problems provably optimal, but on many others it settles for a good answer rather than the best one.
In short
- Greedy means: choose the locally best option, commit, move on.
- It is exactly right for problems with special structure, such as scheduling the most non-overlapping tasks or building a minimum spanning tree.
- On other problems it gives a quick approximation, sometimes with a proven guarantee such as at least half the best value.
- Correctness is usually proved with an exchange argument: swapping any different choice for the greedy one never makes things worse.
What makes an algorithm greedy?
Two habits. At each step it picks the option that looks best given only what it can see right now. And once it has picked, it never goes back. There is no backtracking, no keeping several partial plans alive, no second thoughts.
That makes greedy algorithms a stripped-down relative of dynamic programming, the method Richard Bellman developed in the 1950s for breaking a problem into smaller subproblems and combining their best answers. Dynamic programming keeps track of many partial solutions; a greedy algorithm keeps exactly one. The computer scientist Uriel Feige has described greedy methods as the ultimate form of dynamic programming for that reason, with the catch that the problem needs much more structure for it to work.
A worked example: fitting the most meetings into one room
Imagine one meeting room and five requests: 9:00 to 10:30, 9:30 to 10:00, 10:00 to 11:00, 10:30 to 12:00, and 11:00 to 11:30. You want to host as many meetings as possible with no overlaps.
The greedy rule that works is to sort the meetings by when they end, then repeatedly take the next one that starts after the last chosen one has finished. The earliest finisher is 9:30 to 10:00, so take it. The next that starts at or after 10:00 is 10:00 to 11:00. Then 11:00 to 11:30. Three meetings, and no arrangement does better. Ending early leaves the most room for everything after, which is why this particular greedy choice is always safe.
This is known as the activity selection problem, and it is one of the cleanest cases where greedy is not just fast but exactly right.
Where greedy quietly fails
Change the problem and the same instinct can mislead. Suppose a currency has coins worth 1, 3 and 4, and you need to make 6 with as few coins as possible. Greedy grabs the largest coin that fits, 4, then 1, then 1: three coins. The best answer is 3 plus 3: two coins. The first move looked best and locked in a worse result.
The same pattern shows up in harder problems. In the classic knapsack problem, where each item must be taken whole or left behind, greedy can fall short; the general version is known to be NP-hard. If items can be cut into fractions, though, taking the best value per unit of weight first is provably optimal. In decision-tree learning, popular methods such as ID3 split greedily and are not guaranteed to find the best tree.
Where are greedy algorithms used?
Some of the best-known algorithms in computer science are greedy at heart. Dijkstra's algorithm finds shortest paths by always settling the closest unvisited point next. Prim's and Kruskal's algorithms build a minimum spanning tree, the cheapest set of links that connects every point in a network, by repeatedly adding the cheapest safe edge. Huffman coding builds compact codes for data compression by repeatedly merging the two least frequent symbols.
Greedy routing forwards a message to whichever neighbouring node is closest to the destination. And when exact answers are out of reach, greedy methods give fast approximations for problems such as set cover, load balancing and the travelling salesman. For certain problems the approximation comes with a guarantee: on submodular maximisation, for example, greedy is proven to reach at least half the best possible value.
How do you know a greedy answer is the best one?
There is no general test, because there is no formal definition of greedy that covers every case. But some structures are known to guarantee success. Jack Edmonds showed that problems with a structure called a matroid can be solved greedily, and Bernhard Korte and László Lovász later widened this with the idea of a greedoid.
For a specific problem, the usual proof is an exchange argument. Assume some optimal solution differs from the greedy one, find the first place they differ, and show that swapping in the greedy choice there cannot make the optimal solution worse. Repeat, and the greedy solution is shown to be at least as good as any other. In the meeting-room example, swapping any first meeting for the earliest-ending one never reduces how many meetings fit afterwards.
What does it teach about thinking?
Greedy choices are a superb default when each step does not close off better options later. The question to ask is not whether a move looks best now, but whether taking it could block something better down the line. When it cannot, decide quickly and move on. When it can, as with the coins, a little lookahead is worth its cost.
Questions people ask
Is Dijkstra's algorithm a greedy algorithm?
Yes. At each step it commits to the unvisited point with the smallest known distance and never revisits that decision. With non-negative edge costs this greedy choice is provably correct, which is why Dijkstra's algorithm and the related A* search are standard examples of greedy methods that reach the optimal answer. A* is optimal only when its estimate of the remaining distance never overestimates the true cost.
What is the difference between greedy and dynamic programming?
Both break a problem into smaller decisions. Dynamic programming considers many partial solutions and combines the best answers to overlapping subproblems, so it can recover from a choice that looked good early but was not. A greedy algorithm keeps only one partial solution and never reconsiders it. Greedy is faster and simpler but only correct when the problem has enough structure.
Why use a greedy algorithm if it can be wrong?
Because it is often exactly right, and when it is not, it can still be close enough to be useful in a fraction of the time an exact method would need. For many hard problems no fast exact method is known, so a greedy approximation with a proven bound is the practical choice.
The thinking behind it
It introduces greedy algorithms alongside dynamic programming and Dijkstra's algorithm with simple illustrated examples.
Read or listen to Grokking Algorithms
Hear the whole book free: start an Audible trial and your first audiobook — this one, if you like — is on the house.
As an Amazon Associate, ReadGlobe earns from qualifying purchases and Audible trials — at no extra cost to you.
Sources
- Greedy algorithm — Wikipedia
- Dynamic programming — Wikipedia
How this was made: Amili, an AI writer, wrote this article in its own words from the sources above. Every link was checked before publishing. Spotted an error? Tell us and we will correct it.