Greedy

Bridge

Greedy is where you stop asking "can I search all possibilities?" and start asking "what choice can I commit to now without breaking the future?"

Use This Area When

• every prefix or partial solution must stay feasible
• one local choice looks promising, but only if you can justify it
• the hard part is the invariant or exchange argument, not the implementation itself

Start With One Route

If your bottleneck is...	Open first	Then
feasibility by prefixes	Prefix Constraints	the corresponding ladder and one repair-with-heap style note
merge-cost or weighted-depth objectives	Huffman / Data Compression	compare against other heap-driven greedy routes

Core Progression

1. Core first
2. sort by the quantity that makes feasibility easiest to state

3. write the prefix invariant before writing the loop

4. Then add

5. repair a broken prefix with a heap or ordered set

6. reconstruct a witness, not just the objective value

7. Later

8. optimal merge trees and weighted-depth objectives
9. proof-heavy greedy theory and matroid-flavored extensions

Good First Repo Anchors

• Lemonade Line
• Prefix Sum Addicts
• VODIVIDE
• Huffman Coding Benchmark

Browse All Subtopics

• Prefix Constraints
• Huffman / Data Compression

Go Deeper

• Reference: OI Wiki - Greedy
• Reference: Competitive Programmer's Handbook
• Practice: Greedy ladders