JAVA-205 · Lesson 10 of 12 · 19 min

Greedy algorithms

▶ Video coming soon A video version of this lesson is on the way.

Some problems can be solved by making the choice that looks best right now, again and again, without ever reconsidering. Hamza already does this at the till when he gives change: hand over the biggest coin that fits, then the next biggest, and so on. On Tuesday, November 23, 2027, Ingrid shows him when that kind of shortcut, a greedy algorithm, gives the best possible answer, when it quietly fails, and how to tell the difference. The examples are all from the shop: change at the till, Tamsin's bookings for the one truing stand, and the roads the winter volunteers check for ice.

What makes an algorithm greedy

A greedy algorithm builds a solution one piece at a time, and at each step it takes the piece that looks best by some simple rule, never undoing an earlier choice. Greedy algorithms are usually short and fast, often just a sort followed by a single pass. The catch is that a locally best choice is not always part of a globally best solution. A greedy algorithm is correct only when the problem has the greedy-choice property: some optimal solution always includes the greedy choice, so making it never closes off the best answer.

Making change

The till example first. To give change with the fewest coins, take the largest coin that does not exceed what is still owed, subtract it and repeat. In Canada the penny was withdrawn in 2013, so cash totals are rounded to the nearest 5 cents before change is given, and the coins in a till are the toonie (2 dollars), the loonie (1 dollar), the quarter, the dime and the nickel.

Java Example · Main.java
import java.util.*;

public class Main {
    static final int[] COINS = {200, 100, 25, 10, 5};
    static final String[] NAMES = {"toonie", "loonie", "quarter", "dime", "nickel"};

    static int roundCash(int cents) {
        return (cents + 2) / 5 * 5;
    }

    public static void main(String[] args) {
        for (int owed : new int[] {65, 41, 185, 343}) {
            int left = roundCash(owed), coins = 0;
            List<String> handed = new ArrayList<>();
            for (int i = 0; i < COINS.length; i++) {
                while (left >= COINS[i]) {
                    left -= COINS[i];
                    handed.add(NAMES[i]);
                    coins++;
                }
            }
            System.out.println(owed + " cents (cash " + roundCash(owed) + "): " + coins + " coins " + handed);
        }
    }
}
Output
65 cents (cash 65): 4 coins [quarter, quarter, dime, nickel]
41 cents (cash 40): 3 coins [quarter, dime, nickel]
185 cents (cash 185): 5 coins [loonie, quarter, quarter, quarter, dime]
343 cents (cash 345): 5 coins [toonie, loonie, quarter, dime, dime]

What this code does

roundCash rounds a cash amount to the nearest 5 cents, so 41 cents becomes 40. The loop then hands over as many of each coin as fit, largest first. For the Canadian coins this always gives the fewest coins: 343 cents rounds to 345 and is paid with five coins.

For both Canadian and US coins the greedy method is optimal; such coin systems are called canonical. But the greedy-choice property belongs to the coin values, not to the method. Second Gear's earn-a-bike program gives young volunteers credit vouchers worth 1, 3 and 4 hours, which they trade for a bike. To pay 6 hours with the fewest vouchers, greedy takes a 4 and then two 1s, three vouchers, but two 3s would do it with two.

Java Example · Main.java
public class Main {
    public static void main(String[] args) {
        int[] vouchers = {4, 3, 1};
        int owed = 6, count = 0;
        StringBuilder taken = new StringBuilder();
        for (int v : vouchers) {
            while (owed >= v) { owed -= v; count++; taken.append(v).append(" "); }
        }
        System.out.println("greedy: " + count + " vouchers (" + taken.toString().trim() + ")");
        System.out.println("best:   2 vouchers (3 3)");
    }
}
Output
greedy: 3 vouchers (4 1 1)
best:   2 vouchers (3 3)

What this code does

The same greedy loop takes the 4-hour voucher first because it is the largest that fits, and then needs two 1-hour vouchers. Two 3-hour vouchers would have been better. Greedy is not wrong as a method; it simply lacks the greedy-choice property for these values, and lesson 11 solves the problem exactly.

Scheduling the truing stand

The shop has one wheel-truing stand, and Tamsin collects requests from volunteers who want it on Saturday: each request has a start and an end time. She wants to accept as many requests as possible without overlaps. This is the interval scheduling problem. Several greedy rules sound sensible, such as accept the shortest request first or accept the one that starts earliest, but only one is always optimal: repeatedly accept the request that finishes earliest among those that do not overlap what is already accepted.

Java Example · Main.java
import java.util.*;

public class Main {
    record Slot(String who, int start, int end) {
        public String toString() { return who + " " + start + "-" + end; }
    }

    public static void main(String[] args) {
        List<Slot> requests = new ArrayList<>(List.of(
                new Slot("Ana", 900, 1130), new Slot("Ravi", 930, 1000), new Slot("Mei", 1000, 1100),
                new Slot("Theo", 1030, 1200), new Slot("Lin", 1100, 1130), new Slot("Sam", 1130, 1300),
                new Slot("Ola", 1200, 1230)));
        requests.sort(Comparator.comparingInt(Slot::end).thenComparing(Slot::who));
        List<Slot> accepted = new ArrayList<>();
        int freeFrom = 0;
        for (Slot s : requests) {
            if (s.start() >= freeFrom) {
                accepted.add(s);
                freeFrom = s.end();
            }
        }
        System.out.println(accepted.size() + " accepted: " + accepted);
    }
}
Output
4 accepted: [Ravi 930-1000, Mei 1000-1100, Lin 1100-1130, Ola 1200-1230]

What this code does

Times are written as whole numbers on a 24-hour clock, so 930 means 9:30. Sorting the requests by end time and accepting each one that starts after the last accepted request ends gives Ravi, Mei, Lin and Ola. Four is the most that can fit; accepting Ana's long early request first would have allowed only two.

A timeline from 9:00 to 13:00 with seven horizontal bars, one per request: Ana 9:00 to 11:30, Ravi 9:30 to 10:00, Mei 10:00 to 11:00, Theo 10:30 to 12:00, Lin 11:00 to 11:30, Sam 11:30 to 13:00, Ola 12:00 to 12:30. The bars for Ravi, Mei, Lin and Ola are drawn solid and labelled accepted; the others are dashed. A note says: always take the request that ends first.
Earliest finish first: four non-overlapping requests, the most possible

Why is earliest finish safe? Take any optimal schedule and look at its first request. The greedy first choice finishes no later, so swapping it in leaves at least as much room for everything after, and the schedule is still optimal. Repeating the argument for each later choice shows greedy is optimal. This exchange argument, showing that any optimal solution can be changed into the greedy one without getting worse, is the standard way to prove a greedy algorithm correct.

The cost is dominated by the sort: O(n log n) to sort the requests by end time, then O(n) for one pass. Tamsin's other question, how many stands would be needed to accept every request, has a similar greedy answer, which is this lesson's second exercise.

Connecting every site cheaply: spanning trees

Every winter, two volunteers ride a set of roads on frosty mornings to check whether the cargo bike can get through. Kofi wants the smallest total riding that still keeps every site connected to the shop. A set of edges that connects all the vertices with no cycles is a spanning tree, and one with the smallest total weight is a minimum spanning tree. Two classic greedy algorithms find it. Kruskal's algorithm sorts the edges by weight and adds each one unless it would close a cycle. Prim's algorithm grows a tree from the start vertex, always adding the cheapest edge leaving the tree, much like Dijkstra.

Java Example · Main.java
import java.util.*;

public class Main {
    record Road(int a, int b, int minutes) {}

    static int[] leader;

    static int find(int x) {
        while (leader[x] != x) {
            leader[x] = leader[leader[x]];
            x = leader[x];
        }
        return x;
    }

    public static void main(String[] args) {
        String[] places = {"Shop", "Corktown", "Crown Point", "Kirkendall", "Westdale", "Dundas", "Stoney Creek"};
        List<Road> roads = new ArrayList<>(List.of(new Road(0, 1, 9), new Road(0, 2, 11), new Road(1, 2, 7),
                new Road(1, 3, 12), new Road(0, 3, 23), new Road(3, 4, 10), new Road(4, 5, 14),
                new Road(3, 5, 26), new Road(2, 6, 18), new Road(0, 6, 31)));
        roads.sort(Comparator.comparingInt(Road::minutes));
        leader = new int[places.length];
        for (int i = 0; i < leader.length; i++) leader[i] = i;
        int total = 0;
        for (Road r : roads) {
            int x = find(r.a()), y = find(r.b());
            if (x == y) {
                System.out.println("skip " + places[r.a()] + "-" + places[r.b()] + " (would close a cycle)");
                continue;
            }
            leader[x] = y;
            total += r.minutes();
            System.out.println("keep " + places[r.a()] + "-" + places[r.b()] + " " + r.minutes());
        }
        System.out.println("roads to check: " + (places.length - 1) + ", total " + total + " minutes");
    }
}
Output
keep Corktown-Crown Point 7
keep Shop-Corktown 9
keep Kirkendall-Westdale 10
skip Shop-Crown Point (would close a cycle)
keep Corktown-Kirkendall 12
keep Westdale-Dundas 14
keep Crown Point-Stoney Creek 18
skip Shop-Kirkendall (would close a cycle)
skip Kirkendall-Dundas (would close a cycle)
skip Shop-Stoney Creek (would close a cycle)
roads to check: 6, total 70 minutes

What this code does

Kruskal's algorithm sorts the roads by riding time and keeps each one that joins two groups of places not yet connected. The union-find array leader records which group each place is in, and find follows it to the group's leader, shortening the chain as it goes. Six roads with a total of 70 minutes connect all seven places; every skipped road would have closed a loop.

The union-find structure in that example is worth a note. It keeps groups of elements and answers two questions quickly: which group is x in (find), and merge two groups (union). With the path shortening shown, and with merging smaller groups into larger ones, each operation is close to constant time in practice. Kruskal's whole running time is dominated by sorting the edges: O(E log E).

Is greedy right for this problem?

Greedy rules that work and rules that do not
ProblemGreedy ruleOptimal?
Change with Canadian or US coinsLargest coin firstYes: canonical coin systems
Change with vouchers of 1, 3 and 4Largest voucher firstNo: 6 = 3 + 3, not 4 + 1 + 1
Most non-overlapping bookingsEarliest finish firstYes, by an exchange argument
Most non-overlapping bookingsShortest booking firstNo
Minimum spanning treeCheapest edge that closes no cycle (Kruskal)Yes
Shortest paths, non-negative weightsSettle the nearest vertex (Dijkstra)Yes
Fill a trailer with the most valuable items, whole items onlyBest value per kilogram firstNo: needs dynamic programming

When you suspect a greedy method, try to break it with a small counterexample, as the vouchers did. If you cannot, look for an exchange argument. If you find a counterexample, the problem probably needs either a full search or dynamic programming, which considers every option but avoids repeating work.

Try it yourself

Book the truing stand

Complete schedule(List<Slot> requests) so it returns the largest set of non-overlapping requests, using the earliest-finish rule. A request may start exactly when the previous one ends.

The program should print 3 accepted: [Kim 830-930, Jo 930-1045, Bea 1100-1200].

import java.util.*;

public class Main {
    record Slot(String who, int start, int end) {
        public String toString() { return who + " " + start + "-" + end; }
    }

    static List<Slot> schedule(List<Slot> requests) {
        List<Slot> accepted = new ArrayList<>();
        accepted.add(requests.get(0));
        return accepted;
    }

    public static void main(String[] args) {
        List<Slot> requests = new ArrayList<>(List.of(new Slot("Ali", 800, 1100), new Slot("Kim", 830, 930),
                new Slot("Jo", 930, 1045), new Slot("Dev", 1000, 1130), new Slot("Bea", 1100, 1200)));
        List<Slot> accepted = schedule(requests);
        System.out.println(accepted.size() + " accepted: " + accepted);
    }
}

Try it yourself

How many stands?

Tamsin wants to accept every request. Write standsNeeded(int[][] slots), where each slot is {start, end}: sort by start time, keep a PriorityQueue<Integer> of the end times of stands in use, reuse the stand that frees up earliest when it is free by the new start, and otherwise add a stand. Return the number of stands.

The program should print stands needed: 3.

import java.util.*;

public class Main {
    static int standsNeeded(int[][] slots) {
        return 1;
    }

    public static void main(String[] args) {
        int[][] slots = {{900, 1130}, {930, 1000}, {1000, 1100}, {1030, 1200}, {1100, 1130}, {1130, 1300}, {1200, 1230}};
        System.out.println("stands needed: " + standsNeeded(slots));
    }
}

Common mistakes

  • MistakeAssuming a greedy rule is optimal because it works on one example.

    InsteadLook for a counterexample, and prove correctness with an exchange argument.

  • MistakeScheduling the shortest requests first.

    InsteadAccept the request that finishes earliest.

  • MistakeUsing greedy change-making for any set of coin values.

    InsteadGreedy is optimal only for canonical coin systems; use dynamic programming otherwise.

  • MistakeBuilding a minimum spanning tree without checking for cycles.

    InsteadUse union-find to skip edges whose ends are already connected.

  • MistakeForgetting to sort before a greedy pass.

    InsteadMost greedy algorithms start by sorting by the rule's key.

Summary and key terms

  • A greedy algorithm builds a solution by repeatedly taking the choice that looks best now, never undoing it, and it is correct only when the problem has the greedy-choice property.
  • Largest-coin-first change is optimal for canonical coin systems such as Canadian and US coins but fails for vouchers of 1, 3 and 4 hours.
  • Interval scheduling is solved optimally by accepting the request that finishes earliest, which an exchange argument proves; shortest-first and earliest-start rules fail.
  • A minimum spanning tree connects every vertex with the least total weight; Kruskal's algorithm adds edges in order of weight unless they close a cycle, using union-find, in O(E log E), and Prim's algorithm grows the tree from one vertex.
  • Greedy algorithms are usually a sort and one pass, so they are fast, but always test the rule with small counterexamples.
Greedy algorithm
An algorithm that makes the locally best choice at each step without reconsidering.
Greedy-choice property
The property that some optimal solution includes the greedy choice.
Canonical coin system
A set of coin values for which largest-coin-first change always uses the fewest coins.
Interval scheduling
Choosing the most non-overlapping intervals from a set of requests.
Exchange argument
A proof that any optimal solution can be changed into the greedy one without getting worse.
Spanning tree
A set of edges that connects every vertex of a graph with no cycles.
Minimum spanning tree
A spanning tree with the smallest total edge weight.
Kruskal's algorithm
A greedy algorithm that builds a minimum spanning tree by adding edges in order of weight.
Union-find
A structure that tracks groups of elements and can merge groups and find an element's group quickly.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. Why does greedy fail to pay 6 hours with vouchers of 1, 3 and 4 in the fewest vouchers?

    Show answer

    It takes the 4 first and needs 4 + 1 + 1, but 3 + 3 uses only two.

  2. Which greedy rule maximizes the number of non-overlapping bookings?

    Show answer

    Accept the request that finishes earliest.

  3. How many edges does a spanning tree of 7 vertices have?

    Show answer

    6.

  4. What does Kruskal's algorithm use union-find for?

    Show answer

    To check quickly whether an edge would join two places already connected, closing a cycle.

  5. What usually dominates the running time of a greedy algorithm?

    Show answer

    The initial sort, O(n log n).

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz