14.1 Greedy Algorithms

Prerequisites: Classic Dynamic Programming and Sorting. This page starts with an exchange argument from activity selection, uses a weighted interval scheduling example to show a counterexample, and implements Huffman coding with explicit boundary cases.

The previous chapter's DP maintains multiple candidate states. A greedy algorithm is more decisive: at each step, it makes one choice and never goes back. The code is often shorter, but the correctness conditions are much stricter. You can’t adopt a local rule simply because it "seems reasonable." You must prove that at least one optimal solution includes that choice and that the remaining subproblem is still of the same type.

Activity Selection: Earliest Finish First

The goal is to select as many non-overlapping activities as possible. Intervals are half-open [start, end): one activity may start exactly when another ends. This example requires integer endpoints and start < end; zero-duration activities are outside its contract.

def activity_selection(activities):
    activities = list(activities)
    for start, end in activities:
        if not isinstance(start, int) or not isinstance(end, int) or start >= end:
            raise ValueError("activities require integer start < end")
    ordered = sorted(activities, key=lambda item: item[1])
    selected = []
    last_end = None
    for start, end in ordered:
        if last_end is None or start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

activities = [(540, 630), (570, 660), (630, 690),
              (660, 720), (690, 750), (720, 780)]
assert activity_selection(activities) == [
    (540, 630), (630, 690), (690, 750)
]
assert activity_selection([]) == []

Time is expressed in minutes after midnight, avoiding floating-point confusion like 10.5 between "half past ten" and formatted output. The function copies and sorts the input, leaving the caller's list unchanged. Sorting is O(n log n), followed by an O(n) scan; the input copy and output use O(n) space. Integer times may use another reference point and need not fit within one day.

Let g be the earliest-finishing activity, and suppose an optimal solution starts with o. Since g finishes no later than o, replacing o with g keeps every later activity available and preserves the count. Thus some optimal solution contains g. Remove g and repeat the argument on the remaining compatible activities. This proves the greedy choice for this problem.

DP vs Greedy

Dimension	Dynamic Programming	Greedy
Retain information	Simultaneously compare multiple sub-states	Keep only the currently selected option that has been proven safe
Core of Correctness	Complete state coverage of all valid solutions, no missing transitions	Exchange argument, stays-ahead argument, or problem-specific proof
Complexity	Depends on the number of states and transition costs	Depends on implementations such as sorting, heaps, and scanning
Failure signals	State omission or incorrect computation order	Local choices cannot be swapped into an optimal solution

Weighted Interval Scheduling: Greedy Fails

With activity weights, earliest finish first can fail: one valuable activity may beat several low-value ones. In the example below, the finish-time greedy rule earns 4 while DP earns 100.

def weighted_interval_scheduling(intervals):
    intervals = list(intervals)
    for start, end, weight in intervals:
        if any(not isinstance(value, int) for value in (start, end, weight)):
            raise ValueError("interval fields must be integers")
        if start >= end:
            raise ValueError("interval start must be less than end")
    intervals.sort(key=lambda x: x[1])
    n = len(intervals)
    dp = [0] * (n + 1)
    p = [0] * n
    for i in range(n):
        lo, hi = 0, i - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if intervals[mid][1] <= intervals[i][0]:
                lo = mid + 1
            else:
                hi = mid - 1
        p[i] = hi + 1
    for i in range(1, n + 1):
        dp[i] = max(dp[i - 1], intervals[i-1][2] + dp[p[i-1]])
    return dp[n]

print(weighted_interval_scheduling([(0,2,2),(1,3,100),(2,4,2)]))
# Expected: 100 (Select the middle high-weight interval)

The function sorts a copy, requires integer fields and start < end, and allows negative weights. Selecting nothing is allowed, so empty input returns 0. dp[i] is the best weight for the first i sorted activities. p[i] counts earlier activities ending no later than activity i starts. Selecting that activity reads dp[p[i]]; skipping it retains the preceding prefix answer. Sorting and n binary searches take O(n log n) time; extra space is O(n). The function returns only the weight.

---

Huffman Coding: A Greedy Approach to Data Compression

Assign each character a binary prefix code to minimize the sum of frequency times code length. No codeword may be a prefix of another, allowing consecutive codewords to be decoded. The greedy rule merges the two lowest-frequency nodes at each step.

import heapq
from collections import Counter
from itertools import count

def huffman_codes(text):
    if not isinstance(text, str):
        raise TypeError("text must be a string")
    if not text:
        return {}

    sequence = count()
    heap = [
        (frequency, next(sequence), character)
        for character, frequency in Counter(text).items()
    ]
    heapq.heapify(heap)

    while len(heap) > 1:
        left_frequency, _, left = heapq.heappop(heap)
        right_frequency, _, right = heapq.heappop(heap)
        parent = (left, right)
        heapq.heappush(
            heap,
            (left_frequency + right_frequency, next(sequence), parent),
        )

    codes = {}

    def visit(node, prefix):
        if isinstance(node, str):
            codes[node] = prefix or "0"
            return
        left, right = node
        visit(left, prefix + "0")
        visit(right, prefix + "1")

    visit(heap[0][2], "")
    return codes

assert huffman_codes("") == {}
assert huffman_codes("aaaa") == {"a": "0"}
codes = huffman_codes("this is an example for huffman encoding")
assert set(codes) == set("this is an example for huffman encoding")

The sequence number breaks equal-frequency ties, keeping Python from comparing string leaves with tuple internal nodes. The same input produces the same code table; changing the first-appearance order of tied characters can change the table without changing the optimal total length. Empty text returns an empty table. For one distinct character, this implementation assigns 0. An empty codeword plus a separately stored character count could be shorter; the chosen convention allows decoding one character at a time.

Why is merging safe? An optimal full binary prefix tree has a deepest pair of sibling leaves. Moving the two least frequent characters into those positions cannot increase the weighted path length. Thus some optimal solution makes them siblings; every optimal tree need not arrange them identically. Replacing the pair with a parent weighted by their combined frequency reduces the original cost to the smaller problem’s cost plus those two frequencies, allowing induction. Princeton’s compression course presents Huffman prefix codes and their tree implementation.

For text length N, k distinct characters, and total returned codeword length C, counting, heap merging, and codeword construction take O(N+k log(k+1)+C) time and O(k+C) extra space. The recursive tree may be deep enough to reach Python’s recursion limit under extreme frequency distributions. This function only builds a code table. A complete compressed format also needs encoded data and a tree or code lengths for decoding; those bytes count too.

---

Greedy Correctness Proof Approach

Exchange Argument: Assume the optimal solution doesn't include your greedy choice; swap one of its choices with yours and prove the solution doesn't get worse. Repeat the reasoning to derive an optimal solution that includes the greedy choice.

Decision Tree

Propose a local choice rule
  -> Proof that some optimum is preserved: analyze the remaining problem and cost
  -> Counterexample: revise the rule or examine DP, search, and other methods
  -> Neither proof nor counterexample: keep checking; optimality is unproven

---

Verify the Scheduling Formula

This formula assumes one processor, unit-duration tasks that can be freely reordered, and at least n time units between tasks of the same type. Idle slots are allowed; there are no deadlines, dependencies, or unequal durations. Task labels must be hashable, and the input may be an iterable.

from collections import Counter
def least_interval(tasks, n):
    if not isinstance(n, int) or n < 0:
        raise ValueError("cooldown must be a non-negative integer")
    freq = Counter(tasks)
    if not freq:
        return 0
    max_c = max(freq.values())
    max_n = sum(1 for v in freq.values() if v == max_c)
    return max(sum(freq.values()), (max_c - 1)*(n + 1) + max_n)

print(least_interval(['A','A','A','B','B','B'], 2))
# Expected: 8  (A->B->IDLE->A->B->IDLE->A->B)

Let N be the task count, f the highest frequency, and t the number of types tied at f. Every schedule needs at least N slots. The first f−1 rounds of the most frequent types need cooldown spacing, and the last round needs t positions, giving another lower bound (f-1)(n+1)+t. Place those types in rounds and fill the gaps with other tasks to attain the larger bound: leave idle slots when there are too few tasks, or lengthen the rounds to eliminate idle time when enough tasks exist. The function returns only the minimum length, not a schedule. Empty input returns 0; n=0 returns N. Hash-based counting takes expected O(N+1) time and O(u+1) space for u distinct types. Verify the formula with a small state-space search, then add deadlines and locate the step of the proof that fails.

Move Beyond One-Way Decision Paths

Activity selection can be greedy based on ending time not because "earlier is better" sounds intuitive, but because any optimal solution's first activity can be replaced with the one that ends earliest without reducing available intervals for later activities. With weights, this exchange no longer preserves the objective, so we must return to dynamic programming. Huffman also has its own merging proof; different problems can't share a universal greedy template.

Next, move on to NP-Completeness and Reductions, where you'll learn how to distinguish between "no good algorithm has been found" and "there is evidence of inherent complexity suggesting the problem is hard."