Greedy Algorithms

1Greedy: commit to the locally best choice

A greedy algorithm builds a solution by repeatedly taking the choice that looks best right now and never reconsidering it. That strategy yields a global optimum only when the problem has the greedy-choice property (some optimal solution includes the local pick) and optimal substructure (the rest is an optimal solution to a smaller instance).

Without those properties, a locally best step can lock you out of every optimal completion — coin change with arbitrary denominations is the classic warning. Speed alone does not certify correctness.

Figure. Greedy takes the local pick and never revisits it. That is optimal only when some optimum includes that pick and the rest is an optimum of the leftover instance. Speed alone does not prove either property.

What greedy needs

1. Local ruleDefine what "best right now" means (earliest finish, highest ratio, farthest reach, …).
2. CommitTake that choice permanently; do not branch on alternatives.
3. JustifyArgue greedy-choice + optimal substructure (often via an exchange argument) — or refuse greedy.

2Greedy vs dynamic programming

Dynamic programming explores (or tabulates) multiple choices at each stage and keeps optima for subproblems. Greedy keeps only one choice per stage. That makes greedy faster — often a sort plus a linear scan — but wrong when the discarded branches contained the only optimal answers.

Reach for greedy when you can prove a local rule is safe. Reach for DP when subproblems overlap and the safe move depends on trying more than one option (0/1 knapsack, edit distance, many path counts).

Figure. Greedy commits to a local choice; DP keeps optimal answers for every subproblem when the local choice is unsafe.

3Activity selection by earliest finish

To maximize the number of non-overlapping intervals, sort activities by finish time and scan once: always pick the next activity whose start is \geq the last chosen finish. Earliest finish leaves the most room for future picks — an exchange argument shows some optimal schedule includes the greedy choice.

Sorting costs O(n \log n); the scan is O(n). Sorting by start time instead can fail: a long early starter blocks many short later activities.

Figure. Intervals on a shared time scale (width proportional to duration, x to start). Greedy keeps (1,3) and (4,7); (2,5), (5,9), and (1,8) each overlap a pick.

Earliest-finish scan

1. SortOrder activities by increasing finish time.
2. Pick firstTake the earliest-finishing activity; set last_finish to its finish.
3. ScanWhenever the next activity's start ≥ last_finish, pick it and update last_finish.

Coding lab. Pick the earliest-finish pair runs in the app, with checks on your output.

4Huffman coding with a min-heap

Huffman coding builds an optimal prefix code by greedily merging the two lowest-frequency nodes until one tree remains. Each merge creates a parent whose frequency is the sum of its children; a min-heap (priority queue) supplies the two lightest nodes in O(\log n) per extract.

Total time O(n \log n) for n symbols. The greedy step is safe: an exchange argument shows some optimal code tree combines the two rarest symbols at the deepest level.

Figure. Parents 2, 4, 8 from the ledger. Rarest leaves (1, 1) sit deepest under the first merge.

Merge lightest pair

1. Heap of leavesInsert each symbol's frequency into a min-heap.
2. MergeExtract two minima; create a parent with frequency sum; push the parent back.
3. RepeatUntil one node remains — that is the code tree; depth of a leaf is its code length.

Huffman merge loop

import heapq
def huffman_cost(freqs):
    h = list(freqs)
    heapq.heapify(h)
    total = 0
    while len(h) > 1:
        a = heapq.heappop(h)
        b = heapq.heappop(h)
        parent = a + b
        total += parent
        heapq.heappush(h, parent)
    return total

5When greedy fails: prove or find a counterexample

Greedy needs an exchange argument or an explicit greedy-choice proof. If you cannot prove it, hunt a counterexample. Coin change with denominations [1, 3, 4] and amount 6 is enough: the "largest coin first" rule takes 4+1+1 (three coins) while 3+3 uses two.

Fractional knapsack is safe for ratio greedy; 0/1 knapsack is not. Interval scheduling by earliest finish is safe; by longest interval is not. The pattern is: local density does not always equal global density.

Figure. Largest-first greedy spends three coins; two coins of 3 are enough. A counterexample kills the rule.

Stress-test a greedy rule

1. State the ruleName the local key (largest coin, longest interval, …).
2. Seek a small counterexampleFind an instance where the rule's answer is worse than a known better solution.
3. Or proveExchange argument: transform any optimal solution into the greedy one without loss.

6Jump game: farthest reach

Given nums[i] as the maximum jump length from index i, decide whether you can reach the last index. Track farthest: the rightmost index reachable so far. Scan i from left to right while i ≤ farthest; update farthest = max(farthest, i + nums[i]). If farthest ever reaches the end, return true.

The scan is O(n) and avoids an O(n^2) DP that tries every jump length from every index. The greedy claim: only the farthest frontier matters for reachability.

Figure. Cells are jump lengths. Index 0 reaches through 2; index 1 extends farthest to the last cell.

Farthest-reach scan

1. Initializefarthest = 0.
2. Scan reachable iFor i from 0 while i ≤ farthest, set farthest = max(farthest, i + nums[i]).
3. DecideIf farthest ≥ n−1 at any time, success; if the loop ends with farthest < n−1, failure.

Jump game reachability

def can_jump(nums):
    farthest = 0
    for i, step in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + step)
        if farthest >= len(nums) - 1:
            return True
    return True

7Safe greedy classics: ratios and intervals

Fractional knapsack — you may take a fraction of an item — is solved by sorting on value/weight ratio and filling the bag in that order in O(n \log n). 0/1 knapsack forbids fractions and needs DP. Interval scheduling (activity selection) and Huffman join the "proven greedy" set; Dijkstra is greedy on non-negative weights with a priority queue in O((V+E)\log V).

Memorizing the names is less useful than remembering which constraint makes the proof work: fractions allowed, earliest finish, non-negative edges, lightest-pair merge.

Figure. Classic greedy sorts: density for fractional knapsack, earliest end for intervals, frequency for Huffman.

8When to reach for greedy

Try greedy when the prompt smells like "maximum number of non-overlapping…", "minimum number of… under a matroid-like choice", farthest reach, or Huffman-style repeated merge — and you can cite a known proof or write an exchange argument. Prefer DP when choices interact through a capacity or edit budget you must tabulate.

If a peer proposes a greedy sort key, either prove it or kill it with a three-line counterexample before you ship it in an interview.

Use the When to reach for greedy table: max non-overlapping intervals or farthest-reach jumps → known greedy; 0/1 knapsack or arbitrary coin systems → DP; otherwise prove or counterexample.