Sign in to watch this lesson
Algorithms - Greedy · 4:00
Sort-and-Match Greedy
Most greedy algorithms start by sorting and then sweep once, proved by an invariant that keeps greedy ahead. We find the smallest amount coins [1, 2, 2, 7, 9] can't pay by growing a reach of payable amounts (1, 3, 5, then a gap at 6), pair Ferris-wheel riders [2, 3, 7, 8] lightest-with-heaviest into two gondolas, and hand out tickets from a std::multiset with prev(upper_bound(x)), erasing by iterator because erase by value removes every copy.
You will learn
- Find the smallest amount not formable as a subset sum by sorting and maintaining the reach invariant, with a 64-bit accumulator
- Pair items under a limit with two pointers (lightest with heaviest) and justify it with an exchange argument
- Use std::multiset with prev(upper_bound(x)) to take the largest item <= x, detect 'none' with begin(), and erase by iterator
- Recognise sort-then-sweep problems and state the 'greedy stays ahead' invariant that proves them