Greedy fundamentals

A **greedy algorithm** builds a solution one decision at a time. At each step it takes whatever looks best right now by some simple rule, and it never reconsiders. Contrast this with backtracking from the previous chapter, which tries a choice and undoes it, and with dynamic programming, which compares several choices before committing.

Activity selection is the standard first example: given time intervals, choose as many that do not overlap as possible. The locally best choice is to take the interval that **finishes earliest**, because it leaves the most room for the rest. After taking it, discard everything that overlaps it and repeat. Run the animation and watch the same decision repeated: look at the next interval, keep it if it starts at or after the last chosen finish, skip it otherwise.

Notice what is missing: no recursion, no table, no undo. After sorting, a single pass makes every decision, so the whole algorithm costs O(n log n). That speed is the payoff for the proof obligation the next lessons describe.

1static int selectActivities(int[][] intervals) {
2    int[][] a = intervals.clone();
3    Arrays.sort(a, Comparator.comparingInt(x -> x[1]));     // earliest finish first
4    int count = 0, lastEnd = Integer.MIN_VALUE;
5    for (int[] iv : a) {
6        if (iv[0] >= lastEnd) {                             // compatible with everything chosen so far
7            count++;
8            lastEnd = iv[1];                                // the decision is final: never undone
9        }
10    }
11    return count;
12}

1static int select(int[][] iv, int mode) {      // mode 0: earliest finish (optimal), 1: earliest start, 2: shortest
2    Comparator<int[]> rule = mode == 0 ? Comparator.comparingInt(a -> a[1])
3                           : mode == 1 ? Comparator.comparingInt(a -> a[0])
4                           : Comparator.comparingInt(a -> a[1] - a[0]);
5    Arrays.sort(iv, rule);
6    int count = 0, lastEnd = Integer.MIN_VALUE;
7    for (int[] cur : iv) {
8        if (cur[0] >= lastEnd) {                  // compatible with everything chosen so far (half-open intervals)
9            count++; lastEnd = cur[1];            // choose it
10        }                                         // otherwise skip it
11    }
12    return count;
13}

The **greedy-choice property** says: there is always an optimal solution that contains the greedy choice. If this holds, taking the greedy choice loses nothing, so the algorithm can commit to it and continue with the smaller problem that remains.

The property is a claim about the problem and the rule together, not about the problem alone. Earliest finish time has it for interval scheduling, earliest start time does not. The best value-to-weight ratio has it for the fractional knapsack, but not for the 0/1 knapsack where items cannot be split. Proving the property is the work of the next lesson group: the exchange argument and its relatives.

**Optimal substructure** means that after the greedy choice is made, the remaining problem is a smaller instance of the same problem, and an optimal solution to it combines with the choice to give an optimal solution to the whole. For activity selection, once the earliest-finishing interval is taken, what remains is activity selection on the intervals that start at or after its finish.

Substructure alone is not enough for greedy. Dynamic programming problems have it too (the shortest path through a vertex is built from shortest paths to its predecessors). What distinguishes greedy is that one particular subproblem is guaranteed to be the right one, so the others never need to be solved. Greedy needs both properties; dynamic programming needs only optimal substructure plus overlapping subproblems.

Both techniques exploit optimal substructure. Dynamic programming evaluates **every** candidate first choice, solves the subproblem each leaves, and keeps the best. Greedy picks the one candidate its rule favours and solves only that subproblem. When the greedy-choice property holds the answers agree and greedy is cheaper; when it fails, only dynamic programming is correct.

Coin change shows both sides. Run the animation on the “Canonical system (US coins)” preset: greedy takes 25, 25, 10, 1, 1, 1 for 63 and uses 6 coins, which is optimal. Switch to “Greedy fails (1, 3, 4 for 6)”: greedy takes 4, 1, 1 for 3 coins while 3 + 3 uses only 2. The rule did not change; the coin system did.

1static int greedyCoins(int[] coins, int amount) {         // coins sorted in descending order; -1 if stuck
2    int count = 0;
3    for (int c : coins) {
4        count += amount / c;                                // as many of the biggest coin as fit
5        amount %= c;
6    }
7    return amount == 0 ? count : -1;
8}

A greedy rule is guilty until proven innocent, and the quickest way to convict it is a small counterexample. Try the rules for activity selection in the animation by changing the rule option: earliest start picks the long interval that begins first and blocks everything else (the “Earliest start fails” preset takes 1 interval where 3 fit), and shortest duration picks a short interval sitting in the middle of two longer compatible ones (the “Shortest duration fails” preset takes 1 where 2 fit).

A systematic way to search: write the greedy algorithm, write a slow brute-force version that is obviously correct, and compare them on every input of a small size, or on thousands of random small inputs. A mismatch is a counterexample you can read by eye. Counterexamples are usually tiny: three to five items are almost always enough.

1// brute force for activity selection: try every subset (n <= 20)
2static int bruteMaxActivities(int[][] a) {
3    int n = a.length, best = 0;
4    for (int mask = 0; mask < (1 << n); mask++) {
5        boolean ok = true;
6        for (int i = 0; i < n && ok; i++) {
7            if ((mask >> i & 1) == 0) continue;
8            for (int j = i + 1; j < n && ok; j++) {
9                if ((mask >> j & 1) == 0) continue;
10                ok = a[i][1] <= a[j][0] || a[j][1] <= a[i][0];   // disjoint, touching allowed
11            }
12        }
13        if (ok) best = Math.max(best, Integer.bitCount(mask));
14    }
15    return best;
16}

1static int select(int[][] iv, int mode) {      // mode 0: earliest finish (optimal), 1: earliest start, 2: shortest
2    Comparator<int[]> rule = mode == 0 ? Comparator.comparingInt(a -> a[1])
3                           : mode == 1 ? Comparator.comparingInt(a -> a[0])
4                           : Comparator.comparingInt(a -> a[1] - a[0]);
5    Arrays.sort(iv, rule);
6    int count = 0, lastEnd = Integer.MIN_VALUE;
7    for (int[] cur : iv) {
8        if (cur[0] >= lastEnd) {                  // compatible with everything chosen so far (half-open intervals)
9            count++; lastEnd = cur[1];            // choose it
10        }                                         // otherwise skip it
11    }
12    return count;
13}