Greedy: Take the Best Choice Now

The greedy idea

A greedy algorithm makes the choice that looks best right now and never changes its mind. It's simple and fast – but only correct for some problems.

Making change

To pay 289 with as few notes and coins as possible, take the biggest one that fits, again and again:

public class Main {
    public static void main(String[] args) {
        int[] notes = {500, 200, 100, 50, 20, 10, 5, 2, 1};
        int amount = 289, count = 0;
        StringBuilder used = new StringBuilder();
        for (int note : notes) {
            while (amount >= note) {
                amount -= note;
                count++;
                used.append(note).append(' ');
            }
        }
        System.out.println(count + " pieces: " + used.toString().trim());
    }
}

Output

7 pieces: 200 50 20 10 5 2 2

When greedy fails

Imagine a country with coins 1, 3 and 4, and you must pay 6. Greedy takes 4, then 1, then 1 – three coins. But 3 + 3 is only two! Greedy grabbed the 4 too early and couldn't undo it.

public class Main {
    public static void main(String[] args) {
        int[] coins = {4, 3, 1};
        int amount = 6, count = 0;
        for (int c : coins) {
            while (amount >= c) {
                amount -= c;
                count++;
            }
        }
        System.out.println("greedy uses " + count + " coins, but 3 + 3 needs only 2");
    }
}

Output

greedy uses 3 coins, but 3 + 3 needs only 2

For coin systems like that, you need dynamic programming (Module 18).

A greedy that always works: most meetings in one room

Meetings have start and end times; you want as many as possible in one room. The winning rule: always pick the meeting that ends earliest – it leaves the most time for the rest.

import java.util.Arrays;
import java.util.Comparator;

class ByEnd implements Comparator<int[]> {
    public int compare(int[] a, int[] b) { return Integer.compare(a[1], b[1]); }
}

public class Main {
    public static void main(String[] args) {
        int[][] meetings = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}};
        Arrays.sort(meetings, new ByEnd());
        int freeAt = 0, count = 0;
        for (int[] m : meetings) {
            if (m[0] >= freeAt) {               // starts after the last chosen one ends
                System.out.println("take " + m[0] + "-" + m[1]);
                freeAt = m[1];
                count++;
            }
        }
        System.out.println(count + " meetings");
    }
}

Output

take 1-4
take 5-7
take 8-11
3 meetings

Remember: Greedy is great when you can explain why the best-looking choice is never a mistake. If you can find a counter-example (like coins 1, 3, 4), greedy is wrong for that problem.