Greedy algorithms

Introduction

A greedy algorithm builds its answer one step at a time, always taking the choice that looks best right now, and never going back. Greedy algorithms are simple and fast. The hard part is knowing when they give the right answer.

Many everyday decisions are greedy: pay with the largest note first, or join the shortest queue. Sometimes that gives the best possible result, sometimes it does not, and this lesson is about telling which.

How it works

Coin change: when greedy fails

#include <stdio.h>

int greedy(int coins[], int k, int amount) {
    int used = 0;
    for (int i = 0; i < k; i++) {   // coins are in decreasing order
        while (amount >= coins[i]) {
            amount -= coins[i];
            used++;
        }
    }
    return used;
}

int main(void) {
    int taka[] = {1000, 500, 100, 50, 20, 10, 5, 2, 1};
    printf("1789 taka: %d notes\n", greedy(taka, 9, 1789));
    int odd[] = {4, 3, 1};
    printf("6 with {4, 3, 1}: %d coins (3 + 3 needs only 2)\n", greedy(odd, 3, 6));
    return 0;
}

To pay an amount with the fewest notes, the greedy rule is: take the largest note that fits, again and again. For Bangladeshi notes (1000, 500, 100, 50, 20, 10, 5, 2, 1) this always gives the fewest notes.

But change the coins to 1 and pay 6: greedy takes 4, then 1, then 1, three coins, while 3 + 3 needs only two. Greedy committed to 4 and could never take it back. The next lesson solves this with dynamic programming.

When is greedy right?

A greedy algorithm is correct when the problem has the greedy-choice property: some optimal answer starts with the greedy choice, so taking it never closes the door to the best answer. You show this with an exchange argument: take any optimal answer, swap its first choice for the greedy one, and check that it is still valid and no worse. If you cannot prove it, test the greedy rule on small cases; one counter-example, like the coins above, is enough to reject it.

Famous greedy algorithms you will meet: Dijkstra's shortest paths, Prim's and Kruskal's spanning trees, Huffman coding, and the fractional knapsack.

Syntax

// sort the choices by the greedy rule, then:
for (int i = 0; i < n; i++)
    if (still_allowed(i)) take(i);

Example

#include <stdio.h>

int main(void) {
    int start[] = {1, 3, 0, 5, 8, 5};
    int finish[] = {2, 4, 6, 7, 9, 9};   // sorted by finish time
    int n = 6;
    int last = 0;   // the first activity always fits
    int count = 1;
    printf("take activity 0\n");
    for (int i = 1; i < n; i++) {
        if (start[i] >= finish[last]) {   // starts after the last one ends
            printf("take activity %d\n", i);
            last = i;
            count++;
        }
    }
    printf("%d activities\n", count);
    return 0;
}

Several activities want the same room; each has a start and a finish time. Choose as many as possible that do not overlap. The greedy rule: always pick the activity that finishes first among those that start after the last chosen one ends. Finishing early leaves the most room for the rest.

The activities here are already sorted by finish time; normally you sort them first, so the whole algorithm is O(n log n).

Line by line

1. start and finish hold the activities, already sorted by finish time.
2. last is the most recently chosen activity, and activity 0 is always taken, so count starts at 1.
3. The loop looks at each later activity in finish order.
4. An activity fits when it starts at or after the finish of last.
5. When it fits, the program reports it, makes it the new last, and adds 1 to count.
6. The output lists the chosen activities and how many there are.

Expected result

take activity 0
take activity 1
take activity 3
take activity 4
4 activities

In the real world

Huffman coding, used inside file formats such as gzip and PNG, is a greedy algorithm. Network routing and task schedulers also rely on greedy choices, and when the exact best answer is too expensive, a well-chosen greedy rule often gives a good one quickly.

Common mistakes

• Assuming a greedy rule works because it passed a few examples.
• Choosing the shortest activity first, which can block two others that would both have fitted.
• Forgetting to sort by the greedy rule before the main loop.

Best practices

• Try to break a greedy rule on small cases before trusting it.
• Write down why the first choice is safe.
• Use dynamic programming when choices affect each other.

Summary

A greedy algorithm commits to the best-looking choice at every step. It is correct only when the problem has the greedy-choice property, which you show with an exchange argument, and one counter-example disproves it.

Mark lesson complete