Chapter 61: DSA Greedy Algorithms
DSA Greedy Algorithms – Let’s understand this topic properly and deeply, like I’m sitting next to you with a notebook, explaining slowly, drawing small examples on paper, showing decisions step by step, and most importantly helping you feel when greedy works beautifully and when it completely fails.
Greedy algorithms are among the most elegant, most intuitive, and most dangerous techniques in competitive programming and interviews — elegant because the idea is very simple, dangerous because intuition often tricks you.
1. What is a Greedy Algorithm? (very clear definition)
A greedy algorithm always makes the locally optimal choice at each step, hoping that these local choices will lead to a globally optimal solution.
In simple words:
At every moment, pick the option that looks best right now, without worrying too much about future consequences.
The key belief is:
“If I always take the currently best possible step, the final answer will be the best possible overall.”
This belief is true for some problems and completely false for others — that is why greedy is both powerful and risky.
2. Real-life examples where greedy thinking works perfectly
| Situation | Greedy choice at each step | Why it gives optimal result |
|---|---|---|
| Buying fruits with limited money | Always buy the cheapest fruit available | You get maximum number of fruits |
| Making change with coins (Indian currency) | Always give the largest denomination possible | Gives minimum number of coins |
| Activity selection (meeting rooms) | Always pick the meeting that finishes earliest | Allows maximum number of meetings |
| Fractional knapsack (you can take fraction) | Always take the item with highest value/weight ratio | Maximizes total value |
All these problems have a very nice property:
Making the locally best choice at every step leads to the globally best solution.
3. Classic Greedy Problems (you must know these)
| Problem | Greedy choice | Why greedy works here |
|---|---|---|
| Activity Selection | Select activity that finishes earliest | Leaves maximum time for others |
| Fractional Knapsack | Highest value/weight ratio first | You can take fractions → greedy optimal |
| Huffman Coding | Combine two nodes with smallest frequencies | Gives optimal prefix codes |
| Minimum Spanning Tree (Kruskal/Prim) | Always take cheapest edge that doesn’t form cycle | Greedy choice property + cut property |
| Dijkstra’s shortest path | Always expand closest unvisited node | Non-negative weights → greedy safe |
| Coin change (canonical coins) | Always take largest coin possible | Works for standard coin systems |
4. Classic example where greedy works – Activity Selection
You have n meetings with start time and finish time. You have only one meeting room. Select maximum number of meetings you can conduct without overlap.
Meetings:
| Meeting | Start | Finish |
|---|---|---|
| 1 | 1 | 4 |
| 2 | 3 | 5 |
| 3 | 0 | 6 |
| 4 | 5 | 7 |
| 5 | 3 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 10 |
| 8 | 8 | 11 |
| 9 | 8 | 12 |
| 10 | 2 | 14 |
| 11 | 12 | 16 |
Greedy choice: Always pick the meeting that finishes earliest (among remaining non-overlapping meetings)
Steps:
- Sort by finish time: 1 (fin 4), 2 (fin 5), 4 (fin 7), 7 (fin 10), 8 (fin 11), 9 (fin 12), 11 (fin 16), …
- Pick meeting 1 (finishes 4) Next possible: starts after 4 → meeting 4 (finishes 7)
- Pick meeting 4 (finishes 7) Next possible: starts after 7 → meeting 7 (finishes 10)
- Pick meeting 7 (finishes 10) Next possible: starts after 10 → meeting 8 (finishes 11)
- Pick meeting 8 (finishes 11) Next possible: starts after 11 → meeting 11 (finishes 16)
Selected: meetings 1, 4, 7, 8, 11 → 5 meetings (maximum possible)
Why greedy works here: Choosing the meeting that finishes earliest leaves maximum free time for future meetings → mathematically proven optimal.
5. Classic example where greedy fails badly
Problem: You have to reach a destination. There are petrol pumps on the way.
Greedy idea (wrong): “Always fill petrol at the cheapest pump you see so far”
Suppose prices:
Pump 1: ₹90/litre Pump 2: ₹85/litre Pump 3: ₹95/litre (very close to destination)
Greedy person:
- At pump 1: sees ₹90 → fills full tank
- At pump 2: sees ₹85 → but tank is full → skips
- Reaches destination paying average ₹90
Optimal person:
- At pump 1: fills only enough to reach pump 2
- At pump 2: fills full tank at ₹85
- Reaches destination paying average < ₹85
Greedy failed because it committed too early to a locally good choice.
This is why greedy needs proof that local optimum leads to global optimum.
6. When does greedy work? (the two magic properties)
Greedy algorithms work only when the problem has:
- Greedy choice property A locally optimal choice at each step leads to globally optimal solution.
- Optimal substructure The optimal solution to the problem contains optimal solutions to its subproblems.
Both properties must be mathematically proven — you cannot just “feel” that greedy should work.
7. Summary – Greedy Algorithms in one line each
- Greedy makes the locally best choice at every step
- Works only when greedy choice property + optimal substructure hold
- Time complexity usually very fast: O(n log n) (sorting) or better
- Very dangerous if you apply greedy intuition without proof
- Some classic greedy problems are very easy to prove (activity selection, MST, Huffman)
- Others are very tricky and greedy often fails (fractional vs 0/1 knapsack)
- One of the most loved and most hated topics in interviews — because it looks simple but punishes careless intuition
Would you like to go deeper into greedy algorithms?
Very common next topics:
- Activity Selection problem – full proof why greedy works
- Fractional Knapsack vs 0/1 Knapsack – why greedy succeeds/fails
- Huffman Coding – greedy tree building step-by-step
- Interval Scheduling variations
- How to prove a greedy algorithm is correct
- Common greedy problems that trick people (coin change, Egyptian fractions)
Just tell me which one you want next — I’ll explain it in the same detailed, friendly, teacher style with lots of drawings and examples 😊
