Chapter 57 of 65

Greedy Algorithms

On this page

Imagine a shopkeeper has to give you ₹289 as change, using as few notes and coins as possible.

Without thinking too hard, most people would do this:

Take the biggest note that fits:  ₹200   (remaining 89)
Take the biggest note that fits:  ₹50    (remaining 39)
Take the biggest note that fits:  ₹20    (remaining 19)
Take the biggest note that fits:  ₹10    (remaining 9)
Take the biggest coin that fits:  ₹5     (remaining 4)
Take the biggest coin that fits:  ₹2     (remaining 2)
Take the biggest coin that fits:  ₹2     (remaining 0)

At every step, we simply took the best-looking option right now, and never went back to change an earlier decision.

That style of problem solving is called a greedy algorithm.

A greedy algorithm builds a solution step by step, always making the choice that looks best at the current moment, and never reconsidering earlier choices.

You have already seen greedy algorithms in this course without knowing the name: Prim's and Kruskal's algorithms (Minimum Spanning Tree) and Dijkstra's algorithm are all greedy.


How a Greedy Algorithm Works

Almost every greedy algorithm follows the same pattern:

1. Decide what "best choice right now" means
   (smallest, largest, earliest, highest ratio, ...)
        ↓
2. Usually sort the input by that rule
   (or use a priority queue)
        ↓
3. Go through the items one by one
        ↓
4. Take the item if it is allowed (does not break a rule)
        ↓
5. Never undo a decision

Because there is no going back and no trying of alternatives, greedy algorithms are usually simple and fast, often O(n log n) because of the sorting step.


Greedy vs Backtracking

In the Backtracking chapter, we explored all possible choices and undid the ones that did not work.

Backtracking

Greedy

Tries many choices, undoes bad ones

Makes one choice per step, never undoes

Always finds the correct answer (if it explores everything)

Correct only if the problem has the right properties

Often exponential time

Usually O(n) or O(n log n)

So greedy algorithms trade safety for speed. The big question is: when is the greedy choice safe?


When Does Greedy Work?

A greedy algorithm gives the optimal answer when the problem has two properties.

1. Greedy Choice Property

A globally optimal solution can be reached by making the locally best choice at each step.

In other words, taking the "best-looking" option now never stops you from reaching the best final answer.

2. Optimal Substructure

An optimal solution to the whole problem contains optimal solutions to its smaller subproblems.

After making the greedy choice, what is left is a smaller version of the same problem, and solving it optimally gives the overall optimum.

If either property is missing, greedy can give a wrong answer, and it will not warn you.


When Greedy Fails: A Warning Example

Let's go back to giving change, but with a strange coin system:

Coins: 1, 3, 4
Amount: 6

Greedy (take the biggest coin that fits):

4 → remaining 2
1 → remaining 1
1 → remaining 0

Greedy answer: 4 + 1 + 1 = 3 coins

But the best answer is:

3 + 3 = 2 coins

Taking the biggest coin (4) looked best at that moment, but it forced us into a worse result later.

So the same greedy idea works for Indian currency but fails for {1, 3, 4}. Coin systems where greedy always works (like ₹1, 2, 5, 10, 20, 50, 100, 200, 500) are called canonical coin systems. For general coin systems, we need Dynamic Programming, which we study in upcoming chapters.

Here is a Java program that shows both cases:

import java.util.ArrayList;

class Main {

    // coins must be sorted in descending order
    static ArrayList<Integer> greedyChange(int[] coins, int amount) {

        ArrayList<Integer> used = new ArrayList<>();

        for (int coin : coins) {

            while (amount >= coin) {
                amount -= coin;
                used.add(coin);
            }
        }

        return used;
    }

    public static void main(String[] args) {

        int[] indian = {500, 200, 100, 50, 20, 10, 5, 2, 1};

        ArrayList<Integer> a = greedyChange(indian, 289);
        System.out.println("289 -> " + a + " (" + a.size() + " coins/notes)");

        int[] odd = {4, 3, 1};

        ArrayList<Integer> b = greedyChange(odd, 6);
        System.out.println("6 with {4, 3, 1} -> " + b + " (" + b.size() + " coins)");
    }
}

Output:

289 -> [200, 50, 20, 10, 5, 2, 2] (7 coins/notes)
6 with {4, 3, 1} -> [4, 1, 1] (3 coins)

Lesson: a greedy algorithm that "feels right" can still be wrong. Always test it against small tricky examples, or prove it.


Problem 1: Activity Selection

This is the most famous greedy problem, and a favorite in interviews.

Problem: You are given n activities (meetings, classes, events), each with a start time and an end time. You can attend only one activity at a time. What is the maximum number of activities you can attend?

Activity:  A   B   C   D   E   F
Start:     1   3   0   5   8   5
End:       2   4   6   7   9   9

Which Greedy Rule?

There are several rules we could try:

Rule

Works?

Pick the activity that starts earliest

No. A long early activity can block many short ones.

Pick the shortest activity

No. A short activity can overlap two others that could both have been chosen.

Pick the activity that ends earliest

Yes. It leaves the most time for the rest.

Counterexample for "earliest start":

[0 ─────────────── 10]
  [1─2] [3─4] [5─6]

Earliest start picks only 1 activity, but 3 are possible.

Counterexample for "shortest":

[0 ──── 5]   [6 ──── 11]
       [4 ─ 7]

Shortest picks [4─7], which blocks both others. Best answer is 2.

Step by Step

Sort by end time:

A (1, 2)
B (3, 4)
C (0, 6)
D (5, 7)
E (8, 9)
F (5, 9)

Now go through them, keeping track of when the last chosen activity ends:

A (1, 2): first one, take it.          lastEnd = 2
B (3, 4): 3 ≥ 2, take it.              lastEnd = 4
C (0, 6): 0 < 4, overlaps, skip.
D (5, 7): 5 ≥ 4, take it.              lastEnd = 7
E (8, 9): 8 ≥ 7, take it.              lastEnd = 9
F (5, 9): 5 < 9, overlaps, skip.

Answer: 4 activities (A, B, D, E)

Activity Selection in Java

import java.util.Arrays;

class Main {

    static void selectActivities(int[] start, int[] end) {

        int n = start.length;

        // Store {start, end} pairs so we can sort them together
        int[][] activities = new int[n][2];

        for (int i = 0; i < n; i++) {
            activities[i][0] = start[i];
            activities[i][1] = end[i];
        }

        // Greedy choice: sort by end time
        Arrays.sort(activities, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 1;
        int lastEnd = activities[0][1];

        System.out.println("Selected: (" + activities[0][0] + ", " + activities[0][1] + ")");

        for (int i = 1; i < n; i++) {

            // Pick it only if it starts after the last chosen one ends
            if (activities[i][0] >= lastEnd) {

                count++;
                lastEnd = activities[i][1];

                System.out.println("Selected: (" + activities[i][0] + ", " + activities[i][1] + ")");
            }
        }

        System.out.println("Maximum activities: " + count);
    }

    public static void main(String[] args) {

        int[] start = {1, 3, 0, 5, 8, 5};
        int[] end   = {2, 4, 6, 7, 9, 9};

        selectActivities(start, end);
    }
}

Output:

Selected: (1, 2)
Selected: (3, 4)
Selected: (5, 7)
Selected: (8, 9)
Maximum activities: 4

Here we treat an activity that starts exactly when the previous one ends as non-overlapping (>=). If the problem says touching intervals conflict, use > instead. Always read this detail carefully.

Why "Earliest End" Is Correct

We can prove it with an exchange argument, the standard way to prove greedy algorithms:

  1. Take any optimal schedule. Let its first activity be X.

  2. Let G be the activity that ends earliest overall. Since G ends no later than X, replacing X with G cannot create any overlap with the remaining activities.

  3. So there is an optimal schedule that starts with G. The greedy choice is safe.

  4. Remove G and every activity that overlaps it. The rest is a smaller version of the same problem, and we repeat.

Complexity

Sorting       → O(n log n)
One pass      → O(n)
Total time    → O(n log n)
Extra space   → O(n) for the pairs array

Problem 2: Fractional Knapsack

Problem: A thief has a bag that can carry at most W kg. There are items, each with a weight and a value. The thief is allowed to take a fraction of an item (like taking half a bag of rice). What is the maximum total value?

Item:    0     1     2
Value:   60    100   120
Weight:  10    20    30

Capacity W = 50

The Greedy Rule

Since we can take fractions, what matters is value per kg:

Item 0: 60 / 10  = 6 per kg
Item 1: 100 / 20 = 5 per kg
Item 2: 120 / 30 = 4 per kg

Take the items with the highest ratio first, and fill the remaining space with a fraction of the next item.

Take all of item 0 → value 60,  remaining capacity 40
Take all of item 1 → value 100, remaining capacity 20
Take 20/30 of item 2 → value 120 × 20/30 = 80, remaining 0

Total = 60 + 100 + 80 = 240

Fractional Knapsack in Java

import java.util.Arrays;

class Main {

    static double fractionalKnapsack(int[] value, int[] weight, int capacity) {

        int n = value.length;

        Integer[] idx = new Integer[n];

        for (int i = 0; i < n; i++) {
            idx[i] = i;
        }

        // Greedy choice: highest value per kg first
        Arrays.sort(idx, (a, b) -> Double.compare(
            (double) value[b] / weight[b],
            (double) value[a] / weight[a]
        ));

        double total = 0;
        int remaining = capacity;

        for (int i : idx) {

            if (remaining == 0) {
                break;
            }

            if (weight[i] <= remaining) {

                // Take the whole item
                total += value[i];
                remaining -= weight[i];

                System.out.println("Take all of item " + i + " -> +" + value[i]);

            } else {

                // Take only the fraction that fits
                double part = (double) value[i] * remaining / weight[i];
                total += part;

                System.out.println("Take " + remaining + "/" + weight[i]
                    + " of item " + i + " -> +" + part);

                remaining = 0;
            }
        }

        return total;
    }

    public static void main(String[] args) {

        int[] value  = {60, 100, 120};
        int[] weight = {10, 20, 30};

        System.out.println("Maximum value: " + fractionalKnapsack(value, weight, 50));
    }
}

Output:

Take all of item 0 -> +60
Take all of item 1 -> +100
Take 20/30 of item 2 -> +80.0
Maximum value: 240.0

We sort an array of indexes (Integer[]) instead of the values themselves, so value and weight stay linked. Note that Arrays.sort with a comparator needs an object array like Integer[], not int[].

Time complexity is O(n log n) for sorting plus O(n) for the pass.

The 0/1 Knapsack Trap

Now change one rule: each item must be taken completely or not at all. This is the 0/1 knapsack problem.

Greedy by ratio would take item 0 and item 1:

60 + 100 = 160   (weight 30, and item 2 no longer fits)

But the best answer is item 1 and item 2:

100 + 120 = 220   (weight 50)

Problem

Greedy works?

Correct technique

Fractional knapsack

Yes

Greedy by value/weight ratio

0/1 knapsack

No

Dynamic Programming (Knapsack Problems chapter)

This pair is one of the most popular interview questions about greedy algorithms: two problems that look almost the same, but only one can be solved greedily.


Problem 3: Greedy in Graph Algorithms

Some of the most important graph algorithms you have learned are greedy:

Algorithm

Greedy choice at every step

Kruskal's MST

Take the cheapest remaining edge that does not form a cycle

Prim's MST

Take the cheapest edge that connects a new vertex to the tree

Dijkstra's shortest path

Finalize the unvisited vertex with the smallest distance

Notice that Dijkstra's greedy choice is safe only when all edge weights are non-negative. With negative edges, the greedy property is lost, and we had to switch to Bellman-Ford. This is the same story as the coin example: a greedy rule is only correct under the right conditions.


Problem 4: Huffman Coding (Idea)

Huffman coding is a classic greedy algorithm used in data compression (it is part of formats like ZIP/DEFLATE, JPEG and MP3).

The idea is to give shorter binary codes to more frequent characters.

Repeat until one node is left:
    Remove the two nodes with the SMALLEST frequency (min heap)
    Join them under a new node whose frequency is their sum
    Put the new node back into the heap

Example frequencies:

a: 5   b: 9   c: 12   d: 13   e: 16   f: 45

Greedy merges:

5 + 9    = 14
12 + 13  = 25
14 + 16  = 30
25 + 30  = 55
45 + 55  = 100

The very frequent f ends up near the root (a 1-bit code), while rare characters like a and b get longer codes. This uses the priority queue you learned earlier.


More Classic Greedy Problems

Problem

Greedy rule

Minimum number of platforms (railway station)

Sort arrivals and departures, sweep through time

Job sequencing with deadlines

Take the most profitable job first, schedule it as late as possible

Jump Game

Track the farthest index reachable so far

Gas Station

If the tank goes negative, restart from the next station

Assign Cookies

Sort both arrays, give the smallest cookie that satisfies each child

Non-overlapping Intervals

Same as activity selection: keep intervals with the earliest end

Minimum arrows to burst balloons

Sort by end, shoot at the end of each group


How to Approach a Greedy Problem

  1. Find a candidate rule. Ask: what should I pick first? Earliest end? Largest value? Smallest weight? Best ratio?

  2. Try to break it. Before coding, test the rule on 2 to 4 small tricky inputs. If you find a counterexample, try a different rule.

  3. Convince yourself it is correct. Use the exchange argument: show that any optimal solution can be changed to include the greedy choice without getting worse.

  4. Implement. Usually: sort, then one loop.

  5. If no greedy rule survives, the problem probably needs Dynamic Programming or Backtracking.


Common Mistakes

1. Assuming Greedy Is Always Correct

The coin example {1, 3, 4} and 0/1 knapsack both fail. A greedy rule must be justified.

2. Sorting by the Wrong Key

Activity selection must sort by end time, not start time or duration.

3. Ignoring Ties and Boundaries

Does an activity ending at 4 conflict with one starting at 4? The answer changes >= to >.

4. Integer Division in Ratios

value / weight with two ints throws away the decimal part (100 / 30 = 3). Cast to double first.

5. Overflow in Comparators

Writing (a, b) -> a[1] - b[1] can overflow for very large or very negative values. Integer.compare(a[1], b[1]) is always safe.


Greedy vs Other Techniques

Technique

Idea

Typical speed

Greedy

One locally best choice per step, never undone

Fast, often O(n log n)

Backtracking

Try all choices, undo bad ones

Often exponential

Divide and Conquer

Split into independent subproblems, combine results

Often O(n log n)

Dynamic Programming

Solve overlapping subproblems once and reuse answers

Usually polynomial

We study Divide and Conquer in the next chapter, and Dynamic Programming right after that.


Interview Tips and Practice Problems

  • When you propose a greedy solution, say why it works. Interviewers love hearing "exchange argument" or a quick counterexample for the wrong rules.

  • Interval problems (meetings, balloons, intervals) are very often greedy after sorting by end time.

  • If the problem says "you may take part of an item", think greedy. If it says "take it or leave it", think DP.

Good problems to practice:

  1. Assign Cookies (LeetCode 455)

  2. Jump Game (LeetCode 55) and Jump Game II (LeetCode 45)

  3. Non-overlapping Intervals (LeetCode 435)

  4. Minimum Number of Arrows to Burst Balloons (LeetCode 452)

  5. Gas Station (LeetCode 134)

  6. N meetings in one room, Fractional Knapsack, Minimum Platforms (GeeksforGeeks)


The Main Idea

A greedy algorithm makes the best-looking choice at each step and never looks back.

Choose a greedy rule
        ↓
Sort (or use a priority queue)
        ↓
Take each item if it fits the rules
        ↓
Never undo a choice

Greedy is correct only when the problem has:

1. Greedy choice property
2. Optimal substructure

Key examples:

Activity selection   → sort by end time          greedy works
Fractional knapsack  → sort by value/weight      greedy works
Indian coin change   → biggest coin first        greedy works
Coins {1, 3, 4}      → biggest coin first        greedy FAILS
0/1 knapsack         → by ratio                  greedy FAILS (use DP)

Greedy algorithms are simple and fast, but they are only trustworthy when you can explain why the local choice is always safe. If you can find a counterexample, switch to a different technique.