Greedy Algorithms
A Greedy Algorithm is an algorithm that makes the best choice available at the current moment, hoping that these local best choices will lead to the overall best solution.
The key idea is:
Choose the best now, and never go back to change the choice.
1. Simple Example
Imagine you have:
Coins: ₹1, ₹2, ₹5, ₹10
You need to make:
₹18
A greedy approach chooses the largest possible coin each time:
18 ↓ 10 → remaining 8 ↓ 5 → remaining 3 ↓ 2 → remaining 1 ↓ 1 → remaining 0
Answer:
10 + 5 + 2 + 1 = 18
We always picked the largest available coin.
This is a greedy strategy.
Important: Greedy does not always work for every problem. The algorithm must have the right mathematical properties.
2. Greedy Algorithm Structure
Generally:
Problem ↓ Look at available choices ↓ Choose the best current choice ↓ Make the choice ↓ Move to the next decision ↓ Repeat
Unlike many backtracking algorithms:
Greedy → Choose → Never reconsider
3. Real-Life Analogy
Suppose you are traveling and want to reach a destination.
At every intersection, you choose the road that looks shortest right now.
Current location ↓ Choose shortest-looking road ↓ Next location ↓ Choose shortest-looking road ↓ ...
That's a greedy style of thinking.
But there is a problem:
The shortest-looking road right now may lead to a longer overall route.
Therefore:
Greedy decisions are not automatically optimal.
4. Greedy vs Other Algorithms
Greedy
Best choice NOW ↓ Never change
Backtracking
Try choice ↓ Explore ↓ If wrong → undo ↓ Try another
Dynamic Programming
Break problem into subproblems ↓ Solve/store results ↓ Combine optimal results
A useful mental model:
Greedy → "What is best right now?" Backtracking → "Let me try this and undo if necessary." DP → "What are the best results for smaller problems?"
5. When Does Greedy Work?
A greedy algorithm generally works when the problem has properties such as:
1. Greedy Choice Property
A locally optimal choice can be part of a globally optimal solution.
In simple terms:
Making the best choice now does not prevent us from getting the best final answer.
2. Optimal Substructure
An optimal solution contains optimal solutions to its subproblems.
This property also appears in Dynamic Programming.
6. Activity Selection Problem
One of the most famous greedy problems is:
Select the maximum number of non-overlapping activities.
Suppose we have:
Activity Start End A1 1 3 A2 2 5 A3 4 7 A4 6 8 A5 8 9
We want to attend as many activities as possible.
7. Greedy Idea
Which activity should we choose?
A good greedy strategy is:
Choose the activity that finishes earliest.
Why?
Because finishing early leaves more time for future activities.
Sort by finishing time:
A1 → ends at 3 A2 → ends at 5 A3 → ends at 7 A4 → ends at 8 A5 → ends at 9
Choose:
A1: 1 → 3
Next compatible activity:
A3: 4 → 7
Next:
A5: 8 → 9
Answer:
A1 → A3 → A5
Total:
3 activities
8. Activity Selection Code
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Activity { int start; int finish; }; int main() { vector<Activity> activities = { {1, 3}, {2, 5}, {4, 7}, {6, 8}, {8, 9} }; // Sort by finish time sort( activities.begin(), activities.end(), [](Activity a, Activity b) { return a.finish < b.finish; } ); int count = 0; int lastFinish = -1; for (auto activity : activities) { if (activity.start >= lastFinish) { cout << "(" << activity.start << ", " << activity.finish << ") "; lastFinish = activity.finish; count++; } } cout << "\nMaximum activities: " << count; return 0; }
The important part is:
if (activity.start >= lastFinish)
We only choose an activity that starts after the previous selected activity finishes.
9. Why Earliest Finish?
Imagine:
Activity A: 1 ----------- 10 Activity B: 2 --- 3 Activity C: 4 --- 5
If we choose A:
1 ----------- 10
we lose the opportunity to choose B and C.
If we choose B:
2 --- 3
we still have plenty of time.
So:
Earliest finish ↓ More remaining time ↓ More opportunities
This is the greedy reasoning.
10. Fractional Knapsack
Another famous greedy problem is Fractional Knapsack.
Suppose we have a bag with capacity:
50 kg
Items:
| Item | Weight | Value |
|---|---|---|
| A | 10 | 60 |
| B | 20 | 100 |
| C | 30 | 120 |
In fractional knapsack, we are allowed to take part of an item.
For example:
50% of item C
is allowed.
11. Value per Weight
We calculate:
value / weight
For A:
60 / 10 = 6
B:
100 / 20 = 5
C:
120 / 30 = 4
So:
A → 6 B → 5 C → 4
Choose highest value/weight first.
12. Fractional Knapsack Example
Capacity:
50
Take A:
weight = 10 value = 60 remaining = 40
Take B:
weight = 20 value = 100 remaining = 20
C weighs 30, but only 20 capacity remains.
Take:
20 / 30
of C.
Value obtained:
120 × 20/30 = 80
Total:
60 + 100 + 80 = 240
Answer:
240
13. Fractional Knapsack Code
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Item { int weight; int value; }; bool compare(Item a, Item b) { return (double)a.value / a.weight > (double)b.value / b.weight; } double fractionalKnapsack( int capacity, vector<Item>& items ) { sort(items.begin(), items.end(), compare); double totalValue = 0; for (auto item : items) { if (capacity >= item.weight) { capacity -= item.weight; totalValue += item.value; } else { totalValue += (double)item.value * capacity / item.weight; break; } } return totalValue; }
Complexity:
Sorting = O(n log n) Traversal = O(n) Total = O(n log n)
14. Important: Fractional vs 0/1 Knapsack
This is a very important DSA distinction.
Fractional Knapsack
You can take part of an item:
60% 30% 75%
Greedy works.
0/1 Knapsack
You must either:
Take item → 1 Don't take → 0
You cannot take a fraction.
For 0/1 Knapsack, the simple greedy strategy does not always produce the optimal answer.
It is typically solved using Dynamic Programming.
This distinction is frequently tested in interviews/exams.
15. Coin Change
Greedy can also be used for coin change.
Suppose denominations are:
1 2 5 10
Amount:
18
Choose largest possible:
10
Remaining:
8
Choose:
5
Remaining:
3
Choose:
2
Remaining:
1
Choose:
1
Result:
10 + 5 + 2 + 1
Number of coins:
4
16. But Greedy Coin Change Can Fail
This is extremely important.
Consider coins:
1, 3, 4
Amount:
6
Greedy chooses:
4
Remaining:
2
Then:
1 + 1
So:
4 + 1 + 1
Number of coins:
3
But the optimal answer is:
3 + 3
Only:
2 coins
Therefore:
Greedy does not work for arbitrary coin systems.
17. Greedy Choice Must Be Proven
This is one of the most important lessons.
Don't think:
Greedy = always correct
Instead:
Can I prove that the greedy choice is safe?
For some problems:
Greedy → Correct
For others:
Greedy → Wrong
18. Huffman Coding
Huffman Coding is another important greedy algorithm.
It is used for:
Data compression
Suppose characters have frequencies:
A → 5 B → 9 C → 12 D → 13 E → 16 F → 45
Huffman repeatedly combines the two smallest frequencies.
First:
5 + 9 = 14
Then:
12 + 13 = 25
Then the two smallest available values are combined again.
This creates a Huffman Tree.
Frequent characters receive shorter codes.
For example, conceptually:
F → short code A → longer code B → longer code ...
This reduces the total encoded size.
19. Huffman Greedy Strategy
At every step:
Choose two nodes with smallest frequency ↓ Combine them ↓ Put combined node back ↓ Repeat
A min-heap / priority queue is normally used.
This connects directly to the Heap and Priority Queue topics you already learned.
Greedy + Priority Queue ↓ Huffman Coding
20. Minimum Spanning Tree
Greedy algorithms are heavily used in graph problems.
Two major algorithms for Minimum Spanning Tree are:
Prim's Algorithm Kruskal's Algorithm
Both use greedy ideas.
21. Kruskal's Algorithm
Suppose we have weighted edges:
A --1-- B A --4-- C B --2-- C B --5-- D C --3-- D
Kruskal's idea:
Choose the smallest available edge that does not create a cycle.
Sort edges:
1 2 3 4 5
Then choose:
A-B → 1 B-C → 2 C-D → 3
Now all vertices are connected.
This gives an MST.
Kruskal commonly uses:
DSU / Disjoint Set Union
which you'll encounter later in advanced data structures.
22. Prim's Algorithm
Prim's Algorithm starts from one vertex.
Then repeatedly:
Choose the minimum-weight edge that connects the current tree to a new vertex.
It commonly uses:
Priority Queue
So:
Prim ↓ Greedy ↓ Minimum edge ↓ Priority Queue
23. Dijkstra's Algorithm
You already encountered shortest-path algorithms while learning graphs.
Dijkstra's algorithm also has a greedy idea.
At each step:
Choose the unprocessed vertex with the smallest known distance.
For example:
A → B = 4 A → C = 2
Starting from A:
distance[A] = 0 distance[B] = 4 distance[C] = 2
Choose C because:
2 < 4
Then continue.
Dijkstra is generally used for graphs with non-negative edge weights.
A priority queue is commonly used to efficiently choose the next closest vertex.
24. Greedy Algorithms You've Seen
You should recognize these major examples:
Greedy Algorithms │ ├── Activity Selection ├── Fractional Knapsack ├── Huffman Coding ├── Kruskal's Algorithm ├── Prim's Algorithm ├── Dijkstra's Algorithm └── Some Coin Change Systems
25. Greedy vs Dynamic Programming
This is one of the most important comparisons.
Suppose a problem asks:
Find the maximum possible result.
Greedy
Makes one choice:
Best current choice ↓ Continue ↓ Best current choice ↓ ...
It doesn't normally reconsider previous choices.
DP
Considers multiple possibilities:
Problem / \ Choice A Choice B ↓ ↓ solve solve \ / best result
DP stores results to avoid repeating work.
26. Greedy vs Backtracking
Greedy
Choose ↓ Commit ↓ Continue
Backtracking
Choose ↓ Explore ↓ Wrong? ↓ Undo ↓ Try another
Example:
Activity Selection
Greedy
N-Queens
Backtracking
27. How to Identify a Greedy Problem
When solving a problem, ask:
Question 1
Can I make a decision based on the current situation?
Question 2
Is there an obvious best choice?
For example:
Earliest finish Highest value/weight Smallest edge Closest vertex
Question 3
After making that choice, do I never need to change it?
Question 4
Can I prove that this choice cannot hurt the optimal solution?
If yes, greedy may be appropriate.
28. Common Greedy Strategies
Different problems use different local choices.
Minimum/earliest
Choose smallest Choose earliest
Example:
Activity Selection
Maximum
Choose largest
Example:
Some coin systems
Highest ratio
value / weight
Example:
Fractional Knapsack
Minimum edge
Choose smallest edge
Example:
Kruskal Prim
Minimum distance
Choose closest vertex
Example:
Dijkstra
Minimum frequency
Choose two smallest
Example:
Huffman Coding
29. Advantages of Greedy Algorithms
Simple
Usually easier to understand and implement.
Fast
Many greedy algorithms have efficient complexity.
For example:
Activity Selection → O(n log n)
because of sorting.
Memory efficient
Many greedy solutions require little additional memory.
30. Disadvantages
The biggest problem:
Greedy does not always guarantee an optimal solution.
Example:
Coins: 1, 3, 4 Amount: 6
Greedy:
4 + 1 + 1
Optimal:
3 + 3
So we must determine whether greedy is actually valid.
31. Greedy Complexity
There is no single complexity for all greedy algorithms.
It depends on the problem.
Examples:
Activity Selection → O(n log n) Fractional Knapsack → O(n log n) Kruskal → O(E log E) Prim with priority queue → commonly O(E log V) Dijkstra with priority queue → commonly O((V + E) log V)
32. Greedy Mental Model
Remember this:
GREEDY | Best choice right now | Commit | Don't reconsider | Continue | Final solution
But always ask:
"Is this local choice guaranteed to be safe?"
That's the key to understanding Greedy Algorithms.
Final Summary
GREEDY ALGORITHM │ ├── Make the best local choice │ ├── Usually don't reconsider it │ ├── Often simple and efficient │ └── Must have a valid greedy strategy
Important examples:
| Problem | Greedy Choice |
|---|---|
| Activity Selection | Earliest finish |
| Fractional Knapsack | Highest value/weight |
| Huffman Coding | Two smallest frequencies |
| Kruskal | Smallest safe edge |
| Prim | Cheapest edge to new vertex |
| Dijkstra | Smallest current distance |
| Coin Change | Largest coin — only when valid |
And the most important warning:
A problem looking like it can be solved greedily does not mean greedy is correct. You need a reason/proof that the local choice leads to an optimal global solution.