Greedy with Exchange Argument
Sort by the quantity that makes the local choice obviously safe, then prove swapping any other choice is no better.
GreedyO(n log n)New46 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
minimum number of X
schedule to maximise count
jump game
gas station
The template
Get this into muscle memory, then adapt the condition per problem.
items.sort(byTheRightKey);
let taken = 0, cursor = -Infinity;
for (const it of items)
if (it.start >= cursor) { taken++; cursor = it.end; }If you are stuck
The generic hint ladder for this pattern, in order.
- 1Try the obvious greedy on a small case and look for a counterexample.
- 2The right sort key is usually the constraint you are fighting.
- 3If you cannot justify it, switch to DP.
Drill it
Every problem in the bank that uses this pattern.
0 / 46 solved