Lessons · Python · greedy choices
Take the best step now, and never look back
A greedy algorithm makes the choice that looks best at each step and never reconsiders. That is why it is fast, and why it is sometimes wrong.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
Greedy is the right answer to a real family of problems, and the wrong answer to a family that looks identical. Knowing which is which, and being able to say why, is what an interviewer is actually asking.
How to think about it
State the local rule, then try to break it with a small example. If you can construct a case where the greedy choice loses, you need to search or memoise instead. If you can argue the choice is always safe, say the argument out loud.
Worked example
def greedy_coins(target, coins):Take the largest coin that fits, over and over.
used = 0
for coin in sorted(coins, reverse=True):Biggest first.
used += target // coinAs many of this coin as fit.
target %= coinWhat is left.
return used
print(greedy_coins(30, [25, 10, 1]))6
print(greedy_coins(30, [25, 10, 5, 1]))2
rooms = [(1, 3), (2, 5), (4, 7), (6, 8)]Pick the most non-overlapping meetings.
rooms.sort(key=lambda m: m[1])By EARLIEST END: the provably safe local rule.
taken, free_at = 0, 0
for start, end in rooms:
if start >= free_at: taken += 1; free_at = endFinishing soonest leaves the most room after it.
print(taken)2
Your turn
Sort by the field that makes the greedy choice safe.
meetings.sort(key=lambda m: m[])
Solve one with the tests running
The trap
Greedy on coins 25, 10 and 1 makes 30 out of six coins when three tens would do. The same code on 25, 10, 5 and 1 is optimal. The coin set, not the code, decides.