Greedy
Take the best-looking option now, never revisit it, and prove that committing cannot cost you the optimum.
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
6 left. 4 fits, so take it once: 6 - 4 = 2.
In this order
- GreedyTake the locally best choice and never look back; correct only when an exchange argument holds.
- Activity SelectionSort by finish time; always take the next activity that starts after the last chosen one ends.
- Interval SchedulingMaximum set of non-overlapping intervals; earliest finish first is optimal by an exchange argument.
- Interval PartitioningSort by start; assign each interval to the first room that is free, else open a new room.
- Meeting RoomsMinimum rooms = maximum number of simultaneous meetings; sweep sorted starts and ends.
- Minimum PlatformsArrivals and departures sorted as one event list; the peak number open is the platforms needed.
- Fractional KnapsackSort by value per weight; take whole items until one must be split to fill the remaining room exactly.
- Job Sequencing with DeadlinesRichest job first, placed in the latest free slot before its deadline; no free slot means it is dropped.
- Huffman CodingRepeatedly merge the two least frequent symbols; the merge tree gives prefix-free codes.
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.
Or a different category
Dynamic Programming
No single choice is provably safe, so every option has to stay alive until the end.
Heap Algorithms
The best remaining candidate changes as you commit, so one sort is not enough and the set needs a heap.