Greedy Algorithms and When They Lie

1What greedy actually means

Make the choice that looks best right now, commit to it, and never revisit it. No search, no backtracking, no table.

Formally, a greedy algorithm builds a solution one decision at a time, and each decision is made by a fixed local rule and never undone. Compare that with the other two paradigms in this part of the course:

Greedy is by far the cheapest, and its algorithms are usually four or five lines. The catch is that correctness is not automatic. For DP, if your recurrence is right the answer is right. For greedy, you also need a proof that the local rule never destroys a global optimum — and without that proof you have a heuristic, not an algorithm.

2Two properties, and the exchange argument

A greedy algorithm is correct when two specific things are true. There is a standard proof technique for the harder one.

Greedy needs the same optimal substructure that dynamic programming needs: an optimal solution contains optimal solutions to its subproblems. But it needs one more thing that DP does not.

The greedy-choice property is almost always proved by an exchange argument, which follows the same four steps every time:

# The exchange argument, as a template
#
# 1. Let OPT be any optimal solution.
# 2. Suppose OPT does not make the greedy choice g. It makes some other choice o.
# 3. SWAP: replace o with g inside OPT.
#      - show the result is still VALID (does not break a constraint)
#      - show the result is NO WORSE (its value did not decrease)
# 4. So there is an optimal solution containing g. Recurse on what is left.
#
# If step 3 fails -- the swap breaks validity, or makes the answer worse --
# that failure usually IS your counterexample. Look at it closely.

3Interval scheduling: greed done right

One room, many requests, each with a start and an end. Accept as many as possible. The right sort key is not the obvious one.

Three plausible rules, two of which are wrong:

Earliest finish wins because finishing early is exactly the thing that helps the future: it frees the room sooner and constrains nothing else.

def max_activities(intervals):
    """intervals: list of (start, end). Returns the largest non-overlapping subset."""
    chosen = []
    end_of_last = float("-inf")

    for s, e in sorted(intervals, key=lambda iv: iv[1]):   # by END time
        if s >= end_of_last:                               # no clash
            chosen.append((s, e))
            end_of_last = e

    return chosen

Now change the question slightly and the sort key changes with it. Interval partitioning: schedule every request, using as few rooms as possible.

import heapq

def min_rooms(intervals):
    """Fewest rooms needed to hold every interval."""
    rooms = []                                   # heap of end times, one per room in use

    for s, e in sorted(intervals):               # by START time this time
        if rooms and rooms[0] <= s:              # the earliest-freeing room is free
            heapq.heapreplace(rooms, e)          # reuse it
        else:
            heapq.heappush(rooms, e)             # otherwise open a new room

    return len(rooms)

4Where greed lies

Three problems where the greedy rule is obvious, natural, and wrong.

Coin change. Make an amount with the fewest coins. Greedy takes the largest coin that fits, repeatedly. On British, American or Euro coins this is optimal — those systems were designed to make it so. Change the denominations and it collapses.

# Coins {1, 3, 4}, target 6
#
# Greedy: take 4  ->  2 left
#         take 1  ->  1 left
#         take 1  ->  done.   THREE coins.
#
# Optimal:  3 + 3.            TWO coins.
#
# The 4 was locally the best move and globally the wrong one. Nothing in the
# greedy rule can ever discover that, because it never reconsiders the 4.

0/1 knapsack. Items have a value and a weight, the bag has a capacity, and each item is taken whole or not at all. The natural rule — take the best value-per-kilo first — is wrong:

# Capacity 10
#   item A: value 60, weight 10   -> 6.0 per kg
#   item B: value 55, weight  6   -> 9.2 per kg   <- best density
#   item C: value 20, weight  4   -> 5.0 per kg
#
# Greedy by density: B (55, 6kg), then C fits (20, 4kg) -> 75
# Optimal:           A alone                            -> 60?  no, 75 wins here.
#
# Now shrink C to value 5:
#   Greedy by density: B + C = 60.   Optimal: A alone = 60.  Still tied.
# And with capacity 10, item A (60, 10kg), item B (55, 6kg), item C (5, 5kg):
#   Greedy: B (6kg used), C does not fit in 4kg -> 55
#   Optimal: A -> 60.  Greedy loses.

Longest path. Repeatedly walk to the heaviest unvisited neighbour. This is wrong so immediately that it barely needs a counterexample — one fat edge leads into a dead end while a hundred thin ones would have led onward. Unlike the others, longest path has no efficient correct algorithm at all: it is NP-hard on a general graph. (On a DAG it is linear — Chapter 21.)

5Huffman coding

The greedy algorithm you have used today without knowing it: it is inside zip, JPEG, MP3 and every HTTP response you receive.

The greedy step is beautifully counter-intuitive: instead of deciding the frequent symbols first, Huffman repeatedly grabs the two rarest symbols and merges them into one combined symbol.

import heapq

def huffman_lengths(freq):
    """freq: {symbol: count}. Returns total bits of the optimal prefix code."""
    if len(freq) <= 1:
        return sum(freq.values())         # one symbol still needs one bit each

    heap = list(freq.values())
    heapq.heapify(heap)
    total = 0

    while len(heap) > 1:
        a = heapq.heappop(heap)           # the two RAREST
        b = heapq.heappop(heap)
        merged = a + b
        total += merged                   # every merge deepens both subtrees by one bit
        heapq.heappush(heap, merged)

    return total

The running total is worth understanding, because it is not obvious that summing the merges gives the encoded length. Each merge adds one bit to every symbol underneath it, and there are exactly a + b occurrences underneath. So total += a + b is precisely “one more bit for each of those occurrences”, and the sum over all merges is the weighted depth of the tree — which is the encoded size.

6Deciding what to reach for

A short procedure for a problem you have not seen before.

The honest order of operations, in an interview or at a desk:

1. Write the brute force first, even if only in your head. It defines what “correct” means and gives you something to test against.
2. Guess a greedy rule and try to break it. Two minutes with the checklist in §4. If you break it, you have learned exactly what the difficulty is, which usually points at the DP state.
3. If you cannot break it, sketch the exchange argument. If the swap is obviously valid and obviously not worse, implement greedy and move on.
4. If the exchange fails, go to DP. The reason it failed is normally the extra dimension your DP state needs — “how much capacity is left”, “how many stops have I used”.

>_Playground

The three wrong interval rules, greedy vs optimal coin change on every denomination system, and Huffman on real text.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.