Lesson 33.3 · Greedy Algorithms
Sorting Keys and Two-Pass Greedy
Sort so the greedy choice is the next item; when constraints come from both sides, satisfy them in a left pass and a right pass.
12 min
Think of it like this
Lining up children for a photo where each must be taller than the neighbour they're rated above: first fix everyone against their left neighbour, then fix everyone against their right neighbour, never undoing the first fix.
1.Common shapes
Two sorted lists (cookies, boats): sort both and match with two pointers.
Clever sort key (Queue Reconstruction): sort tall people first, then insert each at index k, because shorter people inserted later don't affect taller people's counts.
Two passes (Candy): a left-to-right pass enforces "higher rating than left neighbour → more candy"; a right-to-left pass enforces the right side, taking the max so both hold.
Smallest first (Hand of Straights): the smallest remaining card must start a group, so build groups from it.
Remember
- The sort order often is the proof.
- Two passes for two-sided constraints.
- The smallest element is forced to start something.
Common mistakes
- Handling both neighbours in a single pass (later changes break earlier ones).