Greedy algorithms

Why a cashier reaches for the biggest coin first

A greedy algorithm builds an answer step by step, always taking the choice that looks best right now and never undoing it. A cashier making 87 cents takes the biggest coin that fits, then the biggest that fits the rest.

It is fast but not always right. With coins of 1, 3 and 4, greedy pays 6 as 4 + 1 + 1, which is three coins, though 3 + 3 needs only two. Dynamic programming would compare both options. Greedy commits and never looks back.

Greedy algorithms

Euro and US coins let the biggest-coin rule give the fewest coins

With euro coins (1, 2, 5, 10, 20, 50 cents) or US coins (1, 5, 10, 25), the greedy rule always gives the fewest coins. Coin sets like these are called canonical, so a cashier or self-checkout can use the rule safely.

Other coin sets break the rule. Britain's coins before 1971 included 30, 24, 12, 6, 3 and 1 pence. For 48p, greedy gives 30 + 12 + 6, which is three coins, but two 24p florins need only two.

Greedy algorithms

Picking the meeting that ends first fits the most meetings in one room

Greedy is correct when some best answer always starts with greedy's choice. Say you have one room and many requested meetings. To fit the most, pick the one that ends earliest, drop every meeting that overlaps it, and repeat.

Here is why that works. Take any best schedule and swap its first meeting for the earliest-ending one. The new meeting ends no later, so it clashes with nothing after it, and the number of meetings stays the same.

So greedy's first pick is always safe, and what's left is the same problem on the remaining time. The payoff is speed: one sort by end time, O(n log n), then a single pass, with no table of subproblems to fill in.