Greedy Algorithms Explained

When Is Greedy Correct?

Greedy works when optimal substructure and greedy choice property hold: a locally best choice leads to a global optimum. Sometimes you prove by exchange argument or induction.

Interval Problems

• Activity selection / non-overlapping intervals: Sort by end time; pick earliest ending that doesn't overlap.
• Merge intervals: Sort by start; merge if current overlaps with last in result.
• Insert interval: Find where new interval fits, merge overlapping.

Scheduling

• Task scheduler with cooldown: Schedule most frequent task first, use slots.
• Minimum number of platforms: Sort arrivals and departures; sweep and count.

Other Greedy Classics

• Jump game I and II: farthest reach.
• Candy distribution: two passes (left-to-right and right-to-left).
• Huffman encoding: repeatedly merge two smallest frequencies.

Summary

If the problem asks for "minimum/maximum number of something" or "can we fit all," consider sorting and a greedy rule. Use Preplume(/) to practice greedy problems.