How does a greedy algorithm work
As we saw with big O, the work piles up fast as the input grows. So what if, instead of weighing every option, you just grabbed whatever looks best right now, at every moment? It's certainly fast. But is it always the right answer?
Grab the best thing right now
Say you need to give 870 won in change. The greedy method is simple: grab the largest coin you can give right now.
One 500, three 100s, one 50, two 10s.
You just grabbed the biggest coin each time, and you were done in no time.
Press the coins from largest to smallest to pick them up. (870 won → 500 · 100 · 100 · 100 · 50 · 10 · 10)
That's a greedy algorithm. It doesn't think far ahead about what will happen; it simply picks what's best at this very moment.
The calculation is light, so the decisions are quick.
It doesn't look at the whole
The real mark of greedy is that it never spreads out the whole map.
At each fork, it just takes one step toward whichever side looks better right now. Since it doesn't look far ahead, there's little to agonize over, and it's fast.
In exchange, it never looks back at a choice once it's made.
At each fork, press the larger number to take one step. You can't see the whole map; you only choose between the two in front of you.
Not looking at the whole is both a strength and a weakness. Speed is the strength.
But because it can't see far, a road that looks good now might turn out to be a dead end later.
Still, for some problems this fast method fits perfectly, almost uncannily so.
When it works well
Say you want to fit as many meetings as possible into one meeting room, with no overlapping times.
The greedy trick is to book the meeting that ends earliest first, because the earlier the room frees up, the more can fit afterward.
Remarkably, this greed gives the truly best answer.
Press the meetings that end earliest first to book them. Overlapping ones drop out automatically, and greedy fills the maximum of 4.
Why is this the right answer? Picking the meeting that ends earliest frees the room as soon as possible.
That leaves the most free time, so the most other meetings can fit into it. That's why being greedy one step at a time still makes the whole schedule the best possible.
For problems like this, greedy is the answer.
A counterexample where it fails
This time the coins are strange: there are only 1, 3, and 4 coins, and you need to give 6 in change.
Going greedy, largest first, you give one 4 and then two 1s, which is three coins. But two 3s would do it with just two coins.
The best move in front of you missed the best overall.
Press both methods to compare: greedy (4·1·1 → 3 coins) and the better way (3·3 → 2 coins). Greedy fell into the trap.
Greedy went wrong because the moment it grabbed the 4, the remaining 2 could only be covered by two 1s.
One big step now ruined what came later. So greedy works with ordinary coins but fails with odd ones like these.
Whether greedy works has to be checked problem by problem.
Summary
In one line, a greedy algorithm "picks whatever looks best right now, at every moment." Since it doesn't look at the whole, it's fast and simple.
For some problems, like making change or booking a meeting room, it's exactly right. But with odd coins or tangled paths, the best move in front of you becomes a trap.
So greedy is fast and often right, but whether it's really right has to be checked for each problem.
Press the four key points in order to sum up: best right now → doesn't look at the whole → often right → sometimes wrong.
If dynamic programming, which we saw earlier, is the careful method that gathers every small answer, greedy sits at the opposite end as the simplest kind of greed: pick what's good now and move on.
It's attractive because it's fast and light, but that very simplicity sometimes leads it into a trap.
Once you have a feel for when it works and when it doesn't, the next lesson shows another trick: rolling the dice to choose.