Greedy Algorithms
Not started yet — 10 problems queued. Partition Labels was deferred under Two Pointers and will count toward this pattern too once it's solved.
Make the locally optimal choice at each step, trusting it leads to a globally optimal solution — only valid when the problem has the "greedy choice property." Proving greedy correctness is usually the hard part, not the code. Sorting first is a very common setup move for greedy problems.
Sub-patterns
- A — Interval Scheduling. Choosing a maximal or minimal set of non-conflicting intervals.
- B — Exchange-Argument Greedy. Proving a local swap can never make the answer worse.
- C — Greedy Plus Sorting. Sort first, then make one linear greedy pass.
- D — Greedy Simulation. Directly simulate the greedy process step by step.
Practice set (10)
- Easy — Assign Cookies, Lemonade Change
- Medium — Jump Game, Jump Game II, Gas Station, Non-overlapping Intervals, Minimum Number of Arrows to Burst Balloons, Partition Labels (deferred under Two Pointers)
- Hard — Candy, Jump Game IV
Interval Scheduling
Choose a maximal or minimal set of non-conflicting intervals.
Exchange-Argument Greedy
Prove a local swap can never make the answer worse — the usual way greedy correctness gets justified.
Greedy Plus Sorting
Sort first, then make one linear greedy pass over the sorted input.
Greedy Simulation
Directly simulate the greedy process step by step rather than reasoning about it abstractly.
Notes from readers
Comments — via GitHub