Greedy algorithms intro

A greedy algorithm makes the locally best choice hoping for a global optimum. Works when problem has greedy choice property and optimal substructure—e.g. activity selection, Huffman coding preview.

When greedy works

Prove exchange argument or stay greedy-safe—otherwise use DP. Counterexample: coin systems {1,3,4} target 6—greedy 4+1+1 beats 3+3 depending on definition; canonical coin systems matter.

Activity selection sketch

Sort by finish time; pick non-overlapping activities greedily—O(n log n) sort + O(n) scan.

Minimum coins (canonical)

#include 
#include 

int main() {
    std::vector coins = {25, 10, 5, 1};
    int amount = 63, used = 0, count = 0;
    for (int c : coins) {
        int take = amount / c;
        count += take;
        amount -= take * c;
    }
    std::cout << "coins used=" << count << " left=" << amount << "\n";
    return 0;
}

Important interview questions and answers

1. Q: Greedy vs DP?
   A: Greedy one decision, no table; DP explores overlapping states when greedy fails.
2. Q: Proof in interviews?
   A: Often cite sorting key + exchange argument—show why local choice safe.

Self-check

1. When is greedy incorrect without proof?
2. What is complexity of sort-then-scan greedy?

Pitfall: Greedy without proof fails coin-change and some scheduling variants—mention counterexamples.