Greedy
Take the best-looking option now, never revisit it, and prove that committing cannot cost you the optimum.
Greedy Choice: Coins where greedy fails
A greedy algorithm builds an answer one step at a time and commits at each step: it takes whatever a fixed rule says is best right now and never reconsiders. That makes it cheap, usually one sort and one pass, so O(n log n) with O(1) extra memory, and it makes it wrong unless the rule is chosen for a reason.
The rule is the whole algorithm, and it is nearly always a sort key. Activity selection sorts by finish time, fractional knapsack by value per unit of weight, job sequencing by profit. Sort by the other obvious quantity instead, shortest activity or earliest start or heaviest item, and you get an algorithm with the same running time that quietly returns a worse answer.
Correctness comes from an exchange argument: take any optimal solution, show that swapping its first choice for the greedy one leaves it no worse, and repeat down the sequence. When no such swap exists, the alternatives have to be carried forward, and carrying alternatives forward is what a dynamic programming table does.
After this you can
- State a greedy rule as a sort key, and name what it is maximising or minimising
- Argue a rule correct with an exchange argument, or produce the counterexample that sinks it
- Recognise the interval family: choosing non-overlapping intervals, packing them into rooms, counting the overlap peak
- Choose between sorting once and keeping a priority queue when the best remaining option changes as you go
In this order
Where people go wrong
A rule that only passes the examples
Greedy coin change is optimal for 1, 5, 10, 25 and wrong for 1, 3, 4: making 6 it takes 4, then 1, then 1, where 3 + 3 is better. Trying a rule on a few inputs proves nothing. The exchange argument does.
Sorting by the wrong key
Activity selection is optimal on finish time and not on start time or duration, because the earliest finish is what leaves the most room for everything after it. Take the key from the proof rather than from intuition.
Carrying the fractional rule into 0/1
Value per weight is optimal when an item can be cut and has no safe first choice when it cannot. 0/1 knapsack needs a table. The ratio rule on it is a good heuristic and not an answer.