DataslopeGreedy Algorithms
Learn local-choice algorithms, exchange arguments, and classic greedy problems in C++
Greedy algorithms make the locally optimal choice at each step, hoping it leads to a global optimum.
Greedy works when local choices are provably safe. Advanced theory connects this to matroids; most proofs use an exchange argument.
Greedy needs proof
A local rule that feels right can still fail.
Counterexample: with coins {1,3,4} and amount 6, greedy takes 4+1+1 (3 coins), but optimal is 3+3 (2 coins).
Activity selection
Sort by end time and scan.
Exchange proof intuition: if an optimal schedule starts with a later-ending activity, swap in the earliest-ending compatible activity. It leaves at least as much room for the rest.
Fractional knapsack
Sort by value/weight ratio and take the densest remaining item, possibly fractionally.
Jump game
Track the farthest reachable index.
Huffman coding
Repeatedly merge the two least frequent nodes using a priority queue. Left/right edges form prefix codes.
Minimum platforms
Sort arrivals and departures; sweep with two pointers.
Implement int maxActivities(std::vector<std::pair<int,int>> intervals) where pair is (start,end).
Implement bool canJump(const std::vector<int>& nums).
Use greedy with coins {1,5,10,25}. Greedy only works for canonical coin systems.
What is greedy's core idea?
Try all answers.
Make the locally best choice repeatedly.
Cache subproblems.
Always use recursion.
Why does {1,3,4} fail for amount 6?
Greedy takes 4+1+1, but 3+3 is better.
There is no 1 coin.
6 is impossible.
Greedy never works.
What does an exchange argument show?
An optimal solution can be transformed to include the greedy choice.
The code has no bugs.
The input is sorted.
The algorithm is recursive.