Greedy approach
A greedy algorithm builds its answer one choice at a time: at every step it takes the choice that looks best right now and never undoes it. That makes it simple and fast, usually a sort and one pass. The hard part is knowing when it is right. Pick a chapter: coins taken biggest first, the same rule failing on other coins, three different rules for fitting meetings into one room, the rule that is safe, and buying the cheapest toys first. In the coin chapters the boxes are the coins and the chips the coins taken; in the meeting chapters each bar is a meeting on a time line (both ends included), a red band the time two meetings clash.
The greedy recipe
- Find the choice that looks best now: the biggest coin, the meeting that ends first, the cheapest toy.
- Sort by it, then walk once: take each item that still fits, skip the rest, never go back.
- Try to break it with a small example. Coins
[1, 3, 4]for 6 break biggest-first; a long early meeting breaks earliest-start. - Check it is safe: some best answer starts with the greedy choice (swap a best answer's first pick for yours and nothing gets worse). If not, try every option (Dynamic Programming).