Lessons · TypeScript · 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 right for a real family of problems and wrong for a family that looks identical. Knowing which is which, and saying 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 a case exists where the greedy choice loses, you need to search or memoise. If the choice is always safe, say the argument out loud.
Worked example
function greedyCoins(target, coins) {Take the largest coin that fits, over and over.let used = 0;
for (const coin of [...coins].sort((a, b) => b - a)) {Biggest first.used += Math.floor(target / coin);As many of this coin as fit.
target %= coin;What is left.
}
return used;
}
console.log(greedyCoins(30, [25, 10, 1]));6
console.log(greedyCoins(30, [25, 10, 5, 1]));2
const rooms = [[1, 3], [2, 5], [4, 7], [6, 8]];Pick the most non-overlapping meetings.
rooms.sort((a, b) => a[1] - b[1]);By EARLIEST END: the provably safe local rule.
let taken = 0, freeAt = 0;
for (const [start, end] of rooms) if (start >= freeAt) { taken++; freeAt = end; }Finishing soonest leaves the most room after it.console.log(taken);2
Your turn
Sort by the field that makes the greedy choice safe.
meetings.sort((a, b) => a[] - b[]);
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.