Intuition The one idea behind all greedy algorithmsA greedy algorithm builds a solution one piece at a time, always taking the choice that looks best right now , and never reconsidering . This only gives the global optimum when the problem has a special structure: the greedy-choice property (a locally optimal choice is part of some global optimum) and optimal substructure (the optimum contains optima of subproblems).
WHY it can fail: greedy never backtracks, so if today's best move poisons tomorrow, you lose. The whole skill is proving that the obvious move is safe — usually by an exchange argument : "take any optimal solution; I can swap in my greedy choice without making it worse."
Given n n n s i s_i s i f i f_i f i maximum number of mutually non-overlapping activities (one resource, e.g. one lecture hall).
Activities (start, finish): A(1,4) B(3,5) C(0,6) D(5,7) E(3,9) F(5,9) G(6,10) H(8,11) I(8,12) J(2,14) K(12,16)
Sort by finish (already sorted). Trace:
Pick A (f=4). last=4.
B start 3 < 4 ✗. C start 0 ✗. D start 5 ≥ 4 ✓ → pick, last=7. Why? first compatible after A.
E,F start <7 ✗. G start 6 <7 ✗. H start 8 ≥7 ✓ → pick, last=11.
I start 8 <11 ✗. J start 2 ✗. K start 12 ≥11 ✓ → pick.
Answer: {A, D, H, K} , size 4. Why optimal? every accepted job frees the maximum future window.
Common mistake Steel-man: "Sort by start time, it's the natural order"Why it feels right: chronological order seems fair, and you process events as they arrive. Why it's wrong: the first-starting activity may be the longest (e.g. C(0,6)) and devour the schedule. Fix: sort by finish ; the earliest finisher is provably safe. Complexity: O ( n log n ) O(n\log n) O ( n log n ) O ( n ) O(n) O ( n )
Knapsack capacity W W W i i i v i v_i v i w i w_i w i fractions of items. Maximize total value ∑ x i v i \sum x_i v_i ∑ x i v i ∑ x i w i ≤ W \sum x_i w_i \le W ∑ x i w i ≤ W 0 ≤ x i ≤ 1 0\le x_i\le 1 0 ≤ x i ≤ 1
Intuition WHY value-per-weight winsEvery kilogram of capacity is a "slot" you sell once. You should fill it with the item paying the most per kilogram : the density v i / w i v_i/w_i v i / w i
Common mistake Steel-man: "0/1 knapsack also solves greedily"Why it feels right: densest-first feels universally optimal. Why it's wrong: with indivisible items you may be forced to leave a gap. E.g. W = 10 W=10 W = 10 W = 50 W=50 W = 50 A ( 60 , 10 ) , B ( 100 , 20 ) , C ( 120 , 30 ) A(60,10), B(100,20), C(120,30) A ( 60 , 10 ) , B ( 100 , 20 ) , C ( 120 , 30 ) A , B A,B A , B C C C fractional (240). But 0/1 greedy gives A + B = 160 A+B=160 A + B = 160 B + C = 220 B+C=220 B + C = 220 Fix: 0/1 needs dynamic programming , not greedy.
W = 50 W=50 W = 50 A ( v = 60 , w = 10 ) A(v=60,w=10) A ( v = 60 , w = 10 ) B ( v = 100 , w = 20 ) B(v=100,w=20) B ( v = 100 , w = 20 ) C ( v = 120 , w = 30 ) C(v=120,w=30) C ( v = 120 , w = 30 ) A = 6 , B = 5 , C = 4 A=6,\ B=5,\ C=4 A = 6 , B = 5 , C = 4 A , B , C A,B,C A , B , C
Take A A A 50 → 40 50\to40 50 → 40 60 60 60 Why? highest density.
Take B B B 40 → 20 40\to20 40 → 20 160 160 160
C C C 20 / 30 = 2 / 3 20/30=2/3 20/30 = 2/3 2 3 ⋅ 120 = 80 \tfrac23\cdot120=80 3 2 ⋅ 120 = 80
Total value = 240 =240 = 240 Complexity O ( n log n ) O(n\log n) O ( n log n )
Given symbols with frequencies f 1 , … , f n f_1,\dots,f_n f 1 , … , f n prefix-free binary code (no codeword is a prefix of another) minimizing total encoded length ∑ f i ⋅ ℓ i \sum f_i \cdot \ell_i ∑ f i ⋅ ℓ i ℓ i \ell_i ℓ i
Intuition WHY merge the two smallestRare symbols can afford long codes; frequent symbols must be short. In the optimal tree the two lowest-frequency symbols are siblings at maximum depth — so we combine them into one super-symbol of frequency f a + f b f_a+f_b f a + f b + = f a + f b += f_a+f_b + = f a + f b
Worked example Worked example — frequencies a:5, b:9, c:12, d:13, e:16, f:45Min-heap merges (pop two smallest):
5+9 = 14 (a,b). Heap: 12,13,14,16,45
12+13 = 25 (c,d). Heap: 14,16,25,45
14+16 = 30 . Heap: 25,30,45
25+30 = 55 . Heap: 45,55
45+55 = 100 = root.
Total cost = 14 + 25 + 30 + 55 + 100 = 224 = 14+25+30+55+100 = 224 = 14 + 25 + 30 + 55 + 100 = 224 Why sum internals? cost identity above.
Resulting lengths: f=1, c=3,d=3,e=3, a=4,b=4. Check: 45 ( 1 ) + 12 ( 3 ) + 13 ( 3 ) + 16 ( 3 ) + 5 ( 4 ) + 9 ( 4 ) = 45 + 123 + 56 = 224 45(1)+12(3)+13(3)+16(3)+5(4)+9(4)=45+123+56=224 45 ( 1 ) + 12 ( 3 ) + 13 ( 3 ) + 16 ( 3 ) + 5 ( 4 ) + 9 ( 4 ) = 45 + 123 + 56 = 224
Common mistake Steel-man: "merge by alphabetical / fixed order is fine"Why it feels right: any prefix tree is decodable, so order seems irrelevant. Why it's wrong: decodability ≠ minimum cost; a fixed-length code wastes bits on rare symbols. Fix: always pull the two minimum frequencies from a priority queue. Complexity O ( n log n ) O(n\log n) O ( n log n )
Recall Feynman: explain to a 12-year-oldActivity selection: you want to watch as many movies as possible in one theater — always pick the movie that ends soonest , so you're free again quickest.
Fractional knapsack: you can scoop powders into a bag; pour in the most expensive-per-gram powder first until the bag is full.
Huffman: you give short secret-codes to words you say a lot and long ones to rare words. To build it, keep gluing together the two rarest words and recombining, so the rarest ones end up deepest (longest codes).
Mnemonic Remember the greedy keys"Finish Fast, Pour Pricey, Merge Mini."
Activity → earliest F inish · Knapsack → highest P rice/weight · Huffman → two M inimum frequencies.
Recall Active recall — close the page and answer
What property must hold for greedy to be optimal?
Why does earliest-finish beat shortest-duration?
Why does 0/1 knapsack break greedy but fractional doesn't?
What's the cost of a Huffman tree in terms of internal nodes?
Greedy algorithm definition Builds solution incrementally, taking the locally best choice and never reconsidering.
Two properties needed for greedy optimality Greedy-choice property + optimal substructure.
Activity selection greedy rule Sort by finish time; repeatedly pick earliest-finishing compatible activity.
Why earliest-finish (not shortest/earliest-start) Finishing first leaves the maximum remaining time window for other activities.
Activity selection complexity O ( n log n ) O(n\log n) O ( n log n ) (sort) +
O ( n ) O(n) O ( n ) scan.
Fractional knapsack greedy rule Sort by value/weight density descending; take items fully, fraction the last.
Why fractional knapsack is greedy-solvable Fractions let you exactly fill capacity with the densest item — exchange argument gives no waste.
Why 0/1 knapsack is NOT greedy Indivisible items can force gaps; needs dynamic programming. Counterexample W=50, A(60,10),B(100,20),C(120,30).
Huffman core step Pop two smallest-frequency nodes from a min-heap, merge into a node of summed frequency, push back; repeat n−1 times.
Huffman total cost formula Sum of frequencies of all internal (merged) nodes.
Why merge the two smallest in Huffman They are the deepest siblings in an optimal tree; merging them adds the least cost per step (exchange argument).
Huffman complexity O ( n log n ) O(n\log n) O ( n log n ) using a binary min-heap.
Prefix-free code meaning No codeword is a prefix of another, so decoding is unambiguous.
General proof technique for greedy correctness Exchange argument — transform any optimal solution into one containing the greedy choice without increasing cost.
Dynamic Programming — needed when greedy fails (0/1 knapsack, edit distance).Priority Queue / Binary Heap — engine behind Huffman's min-extraction.Exchange Argument — universal proof tool for greedy correctness.Sorting Algorithms — the O ( n log n ) O(n\log n) O ( n log n ) Prefix Codes & Information Theory — Huffman approaches the Shannon entropy bound.Minimum Spanning Tree (Kruskal/Prim) — other classic greedy + exchange proofs.
no backtrack, risks failure
Intuition Hinglish mein samjhoGreedy algorithm ka funda simple hai: har step pe jo abhi best dikh raha hai wahi le lo, aur peeche mud ke socho mat. Lekin yeh tabhi sahi answer deta hai jab problem mein do cheezein ho — greedy-choice property (aaj ka best move kisi ek optimal solution ka hissa hai) aur optimal substructure. Proof ka famous tareeka hai exchange argument : koi bhi optimal solution lo, aur dikha do ki greedy ka choice usme swap kar do toh answer kharab nahi hota.
Activity selection mein ek hi hall hai aur max programs fit karne hain. Trick: earliest finish time wala activity pehle pick karo — kyunki jo jaldi khatam hota hai woh sabse zyada future time bacha ke deta hai. Shortest duration ya earliest start se sort karna galat hai, wohi common mistake hai. Fractional knapsack mein bag ki capacity W hai aur items ke tukde le sakte ho — toh value/weight density sabse zyada wala pehle bharo, last item ka fraction le lo. Yaad rakho: 0/1 knapsack (tukde nahi) mein yeh greedy fail karta hai, wahan DP lagta hai.
Huffman coding mein frequent symbols ko chhota code, rare ko lamba code dena hai. Algorithm: ek min-heap banao, baar baar do sabse choti frequency nikaalo, merge karke unka sum wapas daalo — n−1 baar. Total cost = saare internal (merged) nodes ki frequency ka sum. Yeh isliye optimal hai kyunki rare symbols tree mein sabse neeche (deepest) chale jaate hain, jo bilkul wahi hai jo hum chahte hain. Teeno ka mantra: "Finish Fast, Pour Pricey, Merge Mini" — exam mein yeh ratt lo!
