Greedy Algorithms : Making the Best Choice at Every Step

Why should you care?

Many programming problems ask us to make a sequence of decisions:

• Which activity should we choose first?
• Which item should we process next?
• How can we minimize cost?
• How can we maximize profit?
• What is the minimum number of resources required?

One approach is to try every possible combination. But that can quickly become too expensive.

Greedy algorithms provide a powerful alternative:

At every step, make the best choice available right now.

The interesting part is that a greedy algorithm does not simply mean "choose what looks best."

For greedy algorithms to work, the locally optimal choice must lead to a globally optimal solution.

Understanding when this is true—and when it is not—is one of the most important skills in algorithm design.

---

The Problem

Suppose you have several activities:

Activity	Start	Finish
A	1	3
B	2	5
C	4	6
D	6	8
E	5	9

You want to attend the maximum number of non-overlapping activities.

A brute-force approach could try every possible subset.

But there is a much simpler strategy:

1. Choose the activity that finishes earliest.
2. Remove conflicting activities.
3. Repeat.

For the example:

A: 1 → 3
C: 4 → 6
D: 6 → 8

We selected three activities.

The surprising part is that choosing the activity that finishes earliest is not just a reasonable heuristic.

For this particular problem, it can be proven to produce an optimal solution.

That is the foundation of greedy algorithms.

---

The Concept

A greedy algorithm builds a solution step by step.

At every step:

Choose the best option available right now.

It does not normally reconsider previous decisions.

The general structure looks like this:

Start with an empty solution

while the problem is not solved:
    choose the best available option
    make that choice
    update the remaining problem

The key idea is local optimality.

Local vs Global Optimality

A locally optimal choice is the best choice right now.

A globally optimal solution is the best solution overall.

For example:

Greedy:

Step 1 → Best current choice
Step 2 → Best current choice
Step 3 → Best current choice
...
        ↓
   Optimal solution

But this only works when the problem has the right mathematical properties.

---

Simple Explanation

Imagine you are hiking and want to reach the top of a mountain.

At every point, you choose the path that goes uphill the most.

That is a greedy strategy:

"Take the best-looking option right now."

But it may fail.

You could reach a small peak where every available path goes downward, while another path that initially goes slightly downhill would eventually reach the highest mountain.

So:

Greedy choices can be excellent, but they are not automatically correct.

The real question is:

Can we prove that making this local choice never prevents an optimal final solution?

If yes, greedy is a strong candidate.

---

Real-world Analogy

Imagine you are scheduling meetings in a conference room.

You have many meetings, but only one room.

Your goal is to schedule as many meetings as possible.

One strategy would be:

Choose the meeting that starts earliest.

But this can be bad.

Suppose:

Meeting A:  9:00 ───────────────── 17:00

Meeting B:  9:00 ─ 10:00
Meeting C: 10:00 ─ 11:00
Meeting D: 11:00 ─ 12:00

Choosing A because it starts earliest gives you:

1 meeting

Choosing the meeting that finishes earliest gives:

B → C → D

3 meetings

So the greedy rule is not arbitrary.

For this problem:

Always choose the compatible activity that finishes earliest.

This leaves the maximum amount of time for future activities.

---

Code Example

Let's implement the classic Activity Selection Problem.

Input

Activities:

Start:  [1, 3, 0, 5, 8, 5]
Finish: [2, 4, 6, 7, 9, 9]

First, sort activities by their finishing time.

import java.util.*;

class Activity {
    int start;
    int finish;

    Activity(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }
}

public class Main {

    public static void main(String[] args) {

        List<Activity> activities = new ArrayList<>();

        activities.add(new Activity(1, 2));
        activities.add(new Activity(3, 4));
        activities.add(new Activity(0, 6));
        activities.add(new Activity(5, 7));
        activities.add(new Activity(8, 9));
        activities.add(new Activity(5, 9));

        // Sort by finishing time
        activities.sort(
            Comparator.comparingInt(a -> a.finish)
        );

        int lastFinish = -1;

        System.out.println("Selected activities:");

        for (Activity activity : activities) {

            if (activity.start >= lastFinish) {

                System.out.println(
                    activity.start + " -> " + activity.finish
                );

                lastFinish = activity.finish;
            }
        }
    }
}

Output

Selected activities:
1 -> 2
3 -> 4
5 -> 7
8 -> 9

We selected four non-overlapping activities.

Why does it work?

After sorting by finish time:

Choose earliest finishing activity
        ↓
It leaves maximum time remaining
        ↓
Choose next compatible activity
        ↓
Repeat

This is a greedy strategy.

---

Proving the Greedy Choice

This is where greedy algorithms become interesting.

Suppose the activity that finishes earliest is:

A

Consider an optimal solution.

If that optimal solution already starts with A, we're done.

If it starts with another activity B that finishes later:

A finishes at 3
B finishes at 5

We can replace B with A.

Since A finishes earlier, replacing B with A cannot reduce the number of activities that can be scheduled afterward.

Therefore, there exists an optimal solution that begins with A.

This is called the greedy-choice property.

Once we make that choice, the remaining problem has exactly the same structure:

Choose the next compatible activity

This gives us the optimal substructure needed for the greedy solution.

---

Common Mistakes

Mistake 1: Assuming every optimization problem can be solved greedily

This is the biggest mistake.

Consider the coin-change problem.

Coins:

1, 3, 4

Target:

6

A greedy algorithm chooses:

4

Remaining:

2

Then:

1 + 1

Total:

4 + 1 + 1 = 3 coins

But the optimal solution is:

3 + 3 = 2 coins

So greedy fails here.

The lesson:

A greedy-looking strategy must be proven correct for the specific problem.

---

Mistake 2: Confusing greedy with brute force

Greedy does not try every possibility.

Brute force:

Try A
Try B
Try C
Try A + B
Try A + C
Try B + C
...

Greedy:

Choose best current option
Choose best current option
Choose best current option

This is why greedy algorithms are often much faster.

---

Mistake 3: Choosing the largest immediate value

"Best" does not always mean:

largest number

or:

smallest number

The correct greedy criterion depends on the problem.

Examples:

Problem	Greedy choice
Activity Selection	Earliest finish time
Fractional Knapsack	Highest value/weight
Huffman Coding	Lowest frequencies
Dijkstra	Smallest current distance
Minimum Spanning Tree	Safest minimum-cost edge
Job Scheduling	Depends on objective

The hardest part is often identifying the correct greedy rule.

---

Advanced Notes

1. Greedy-Choice Property

A problem has the greedy-choice property when making the locally optimal choice can lead to a globally optimal solution.

The important phrase is:

"can lead to an optimal solution."

It does not mean that every arbitrary greedy choice works.

---

2. Optimal Substructure

A problem has optimal substructure when an optimal solution contains optimal solutions to its subproblems.

For example:

Optimal solution
       ↓
Greedy choice
       +
Optimal solution to remaining problem

Both properties are commonly used when proving greedy algorithms.

---

3. Fractional Knapsack

Suppose you have a bag with capacity:

50 kg

and items:

Item	Weight	Value
A	10	60
B	20	100
C	30	120

In fractional knapsack, you can take part of an item.

Calculate:

Value / Weight

Item	Value/Weight
A	6
B	5
C	4

Take:

A → 10 kg
B → 20 kg
C → 20 kg

Total:

50 kg

Value:

60 + 100 + 80 = 240

The greedy rule is:

Take the item with the highest value-to-weight ratio first.

This works for fractional knapsack.

But it does not work for the 0/1 Knapsack problem, where an item must be taken completely or not at all.

That distinction is extremely important.

---

4. Huffman Coding

Greedy algorithms are also used in data compression.

Huffman coding repeatedly combines the two least-frequent symbols.

For example:

A → 45
B → 13
C → 12
D → 16
E → 9
F → 5

The algorithm repeatedly chooses the two smallest frequencies and combines them.

This produces a prefix-free binary tree where frequently occurring characters receive shorter codes.

The greedy choice leads to an optimal prefix code.

---

5. Minimum Spanning Tree

Greedy algorithms are fundamental to graph algorithms.

Two famous algorithms are:

Kruskal's Algorithm
Prim's Algorithm

Kruskal repeatedly chooses the lowest-weight edge that does not create a cycle.

Prim repeatedly chooses the cheapest edge that expands the current tree.

Both rely on greedy choices.

---

6. Dijkstra's Algorithm

Dijkstra's shortest-path algorithm also uses a greedy strategy.

At each step:

Choose the unvisited vertex
with the smallest known distance.

Then update its neighbors.

For graphs with non-negative edge weights, this greedy decision can be proven correct.

However, if negative edge weights exist, standard Dijkstra's algorithm is not valid.

---

7. Greedy vs Dynamic Programming

Greedy and Dynamic Programming are often confused.

Greedy	Dynamic Programming
Makes one choice and commits	Considers multiple possibilities
Usually doesn't revisit choices	Stores/reuses subproblem results
Often simpler	Usually more complex
Can be very fast	Often uses more memory
Requires greedy-choice property	Uses overlapping subproblems + optimal substructure

A useful question is:

Can I safely commit to the best choice now?

If yes, greedy may work.

If not, dynamic programming may be necessary.

---

8. Greedy vs Backtracking

Backtracking explores choices and can undo them.

Choose
 ↓
Explore
 ↓
Wrong?
 ↓
Undo
 ↓
Try another

Greedy:

Choose
 ↓
Commit
 ↓
Never undo

This makes greedy algorithms much more efficient when their correctness can be guaranteed.

---

9. Complexity

Many greedy algorithms have excellent performance.

For activity selection:

Sorting: O(n log n)
Selection: O(n)

Therefore:

Total = O(n log n)

If activities are already sorted by finish time:

O(n)

The greedy decision itself is often cheap.

The expensive part is frequently sorting the input.

---

10. How to Recognize a Greedy Problem

When facing an optimization problem, ask:

1. What am I trying to maximize/minimize?

2. What is the best choice I can make right now?

3. If I make that choice, can I safely discard the alternatives?

4. Does the remaining problem have the same structure?

5. Can I prove that replacing the first choice
   with my greedy choice never makes the solution worse?

That last question is especially important.

Do not use greedy simply because the solution "looks right."

Try to prove it.

---

The Bigger Picture

Greedy algorithms fit into a larger algorithm-design progression.

You have already learned several fundamental techniques:

Arrays
   ↓
Linked Lists
   ↓
Stacks / Queues
   ↓
Trees / Graphs
   ↓
Searching
   ↓
Sorting
   ↓
DFS / BFS
   ↓
Greedy Algorithms

Now the focus changes.

Previously, we often asked:

"How can I efficiently process the data?"

With greedy algorithms, we start asking:

"How can I make the right decisions efficiently?"

This is a major transition from learning data structures to learning algorithmic problem solving.

Greedy algorithms also prepare you for more advanced concepts:

Greedy
   ├── Activity Selection
   ├── Fractional Knapsack
   ├── Huffman Coding
   ├── Dijkstra
   ├── Prim
   └── Kruskal
          ↓
Dynamic Programming
          ↓
Advanced Algorithm Design

---

The Most Important Mental Model

Think of a greedy algorithm as:

"Make the best decision you can prove is safe, then never look back."

The phrase "you can prove is safe" is the most important part.

Greedy is not:

Pick what looks best.

It is:

Pick what is provably safe and optimal at this step.

---

Summary

Greedy algorithms solve optimization problems by repeatedly making a locally optimal choice.

Key ideas:

• Greedy algorithms make decisions step by step.
• They generally do not reconsider previous decisions.
• Local optimality does not automatically guarantee global optimality.
• Correct greedy algorithms require a justification or proof.
• The greedy-choice property is central to greedy correctness.
• Optimal substructure is commonly present.
• Activity Selection is a classic greedy problem.
• Fractional Knapsack can be solved greedily.
• 0/1 Knapsack cannot generally be solved using the same greedy strategy.
• Huffman Coding, Dijkstra, Prim, and Kruskal use greedy ideas.
• Sorting is often the main cost of a greedy solution.
• Greedy is different from Dynamic Programming and Backtracking.