Where it runs
1. The problem
Many scheduling and graph problems are solved like this: at each step, take the option that looks best right now. That is the greedy approach. It always needs a reason: why the choice that is best at one step does not spoil the whole answer.
A cashier in an American shop owes you 40 cents in change. The coins there are 25, 10, 5 and 1 cent. The cashier does not count out forty one-cent coins. They take a 25, then a 10, then a 5, and they are done: three coins. Nobody taught them an algorithm. Again and again they take the biggest coin that is not more than what is still owed, until the change is paid.
You want the same thing in code. You have the coin values a machine holds and an amount to pay out. Pay it with the fewest coins. An ATM solves this every time it counts out notes. A vending machine solves it every time it drops your change.
The rule "take the biggest" almost always gives the best answer. In this lesson you learn on which coin sets it works and on which it goes wrong.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedminCoinsGreedy([1, 5, 2, 10], 18)Pay 18 with as few coins as possible. Greedy rule: always take the biggest coin that still fits.
Bars: when each meeting ends, in the order the meetings start.
One operation is one meeting checked or one comparison while sorting. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(2ⁿ·n)O(n log n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- fewest coins or pieces to make an amount
- largest that still fits, taken greedily
- make change with denominations
- prove optimality with an exchange argument
Looks similar, isn't
- Dynamic programming (1-D)
DP keeps every option open until the end. Greedy commits at once and cannot undo.
- Backtracking
Backtracking tries every choice and keeps the best. Greedy tries one and trusts it.
- Sort with a custom comparator
Most greedy solutions begin with a sort. The comparator is where the choice is written.
- Binary search on the answer
There the feasibility test is often greedy itself. The search only picks the value to test.
O(n log n) when the input has to be sorted first. The pass afterwards is a single loop, O(n).
On LeetCode
Problems where one simple rule, such as the biggest first or the smallest first, gives the best answer. Before you trust the rule, run the exchange argument and show that swapping its choice for any other never makes the answer better. Coin Change itself fails this check and comes in lesson 112.
Give change for a 20 as a 10 and a 5 before three 5s, the lesson's biggest coin first, because only 5s can change a 10.
Sort both lists and give each child the smallest cookie that is big enough. A bigger cookie spent there could only block a later child.
Sort the prices from high to low and take every third candy free, so each free one is as expensive as the rules allow.
Sort the people, put the heaviest with the lightest when they fit, and send the heaviest alone when they do not.