Greedy algorithms

A greedy algorithm builds its answer one step at a time. At each step it takes the option that looks best right now, the greedy choice, and never revisits it. There is no search over alternatives and no backtracking, so it is usually a sort followed by a single O(n) pass.

The catch is that "looks best now" is often wrong. Paying 6 with coins 1, 3 and 4, taking the largest coin first gives 4 + 1 + 1, three coins, while 3 + 3 needs two. So a greedy solution comes with a reason it is safe. The usual one is an exchange argument: take any best answer that differs from yours at the first choice, swap your greedy choice into it, and show the result is no worse. If that always works, some best answer starts with your choice, and the same reasoning covers every step after it.

Each child needs a cookie of at least a certain size, and each cookie goes to one child at most. Sort both lists. Take the cookies from smallest up: if a cookie is big enough for the least demanding child still waiting, give it to that child. If it isn't, no one else can use it either, since everyone left needs more, so skip it.

The exchange argument: in any best answer, the smallest useful cookie could be handed to the least demanding child instead, and no child loses out. So the greedy pairing is as good as any.

Each cell holds the longest jump you may take from it. Can you get from the first cell to the last? Trying every sequence of jumps explodes. The greedy view needs one number: the farthest cell reachable so far. Every cell up to it is reachable too, so walk left to right, stretching that number. If you ever stand past it, you are stuck.

The zeros are not traps as long as an earlier cell jumps over them. The greedy choice here is not a jump at all: it is the decision to remember only the reach, which is all that matters for the question.

Children stand in a row with ratings. Each gets at least one candy, and a child rated higher than a neighbor must get more than that neighbor. Find the fewest candies. One pass can't see both neighbors at once, so split the rule: a left-to-right pass makes every child beat a lower-rated left neighbor, then a right-to-left pass fixes the right neighbors, keeping the larger of the two counts so the first pass is not undone.

Each count is the smallest that satisfies its rule, and taking the larger of the two satisfies both, so no child gets more than necessary. Two O(n) passes in all.

Before writing it, name the key and say why the item that comes first under it is safe to take. Most greedy bugs are a wrong key: by start time instead of end time, by size instead of size per unit.