Ugenz Academy/Tutorial

Greedyalgorithms

13 min read2,428 words

Reading progress

Keep learning

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:

ItemWeightValue
A1060
B20100
C30120

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:

ProblemGreedy Choice
Activity SelectionEarliest finish
Fractional KnapsackHighest value/weight
Huffman CodingTwo smallest frequencies
KruskalSmallest safe edge
PrimCheapest edge to new vertex
DijkstraSmallest current distance
Coin ChangeLargest 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.

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy