Internship← Competitive Programming learning pathCompetitive Programming · Module 6 of 10
Greedy algorithms
Make the best local choice when it is provably safe.
📖 Key ideas
- Greedy picks the best option now and never looks back.
- Activity selection: pick the interval that ends earliest.
- Coin change is greedy only for some coin systems.
- Prove greedy with exchange arguments or counterexamples.
- Sorting by a key is often the first greedy step.
💡 Real-life example: Greedy is like filling a bag with the most valuable items first: great sometimes, wrong when items do not split.
Greedy choiceBest local option now
Exchange argumentProof that swapping does not improve
Activity selectionEarliest finish first
CounterexampleInput where greedy fails