GreedyTake the best step available, now
Greedy algorithms never backtrack and never try alternatives, so they are usually the fastest thing you can write. The catch is that they are not always right. The point of this topic is not just writing a greedy solution, but learning to use an exchange argument to tell when greed is safe.
Why learn Greedy
Where it shows upGiven a pile of meeting times, how many can you fit without a clash? Always take the one that ends earliest — an intuitive rule that can actually be proven optimal.
→ Lesson: Interval SchedulingFrequent characters get short codes, rare ones get long codes. Huffman coding merges the two least frequent each step — greedy, and provably optimal.
→ Lesson: Huffman CodingA till hands out the largest coin first; an OS runs the shortest job first. Some of these are always right and some break on particular coin sets — telling which is the point of this topic.
→ Lesson: Coin Change (Greedy)Each cell says how far you may jump. Track only "the furthest I can currently reach" and one pass answers it, without trying any individual route.
→ Lesson: Jump Game