Greedy algorithms

1 · The greedy-choice property advanced

Start with the moment greedy burned someone — maybe you. You need to make change for 63 cents and you grab coins largest-first: a 50, a 10, and three 1s — five coins, obviously optimal. That habit is so reliable with real currency that you stop thinking about it. Then one day the coin set is {1, 3, 4} and you need 6. Largest-first grabs a 4, then two 1s — three coins — while the real answer is two 3s. The exact same "always take the biggest" rule that was provably optimal a second ago is now just wrong. Nothing about the algorithm changed; the problem did. That gap is the whole reason this section exists before any code: greedy is not a technique you apply, it's a claim you must earn.

Here's the everyday analogy that makes the danger tangible. Greedy is like driving toward a mountain by always turning onto whichever road climbs most steeply right now. On a simple hill that walks you straight to the summit. But on real terrain the steepest local road can dead-end you on a minor peak with a valley between you and the true top — and because greedy "never looks back," you're stuck. Whether local-steepest reaches the summit is a property of the landscape, not of your enthusiasm for climbing. The common mistake, and it is everywhere in production code, is assuming that because a greedy rule feels obviously right on your test cases, it is right in general. It usually isn't — and the failure only shows up on an input you didn't try.

So a greedy algorithm is correct only if two things hold, and you should think of them as proof obligations you owe before you ship. Optimal substructure (shared with DP): an optimal solution contains optimal solutions to subproblems. Greedy-choice property: a globally optimal solution can be reached by making the locally optimal choice at each step — you never need to reconsider. The second is the hard one and the one people skip. It says something remarkable — that a decision made with zero information about the future can never be regretted — and remarkable claims need proof. DP tries all choices and keeps the best; greedy proves that one choice is always safe, so it skips the search entirely. That skipped search is exactly why greedy is the fastest paradigm when it works (often Θ(n log n) where DP is Θ(n²) or worse) and exactly why it's silently wrong when it doesn't. The payoff of proving the property is speed you can trust; the cost of assuming it is a bug that passes every test and fails in the field.

2 · Activity selection — earliest finish wins intermediate

Picture a single conference room and a stack of booking requests. Everyone wants it; the requests overlap in a tangle. Your job is to say yes to as many meetings as possible (not the longest, not the most important — the most meetings). Sit with that for a second and your instinct will probably reach for one of two rules: "let in whoever asks first," or "let in the shortest meetings so I can pack more." Both feel reasonable. Both are wrong, and that is the entire lesson of this section — the obvious greedy rule is not the correct one.

The rule that actually works is almost counterintuitive: always take the activity that finishes earliest among those still compatible with what you've already booked. Why finish time and not start time? Because the resource you're rationing isn't "who's polite enough to ask first," it's the room's future. Every meeting you accept costs you the room until it ends, so the cheapest possible commitment — the one that frees the room soonest for everything after — is the one that ends earliest. Finishing early is greedy's way of "keeping the most options open." That reframing ("what am I actually spending?") is the move you'll make in every greedy problem: find the resource, then pick the choice that consumes the least of it.

The formal statement: given activities with start/finish times, pick the largest set that don't overlap. Sort by finish time and sweep, keeping each activity whose start is at or after the last kept finish — that's Θ(n log n), dominated by the sort. Below the exchange proof shows why earliest-finish is safe, and the warning box after the code shows concrete inputs where start-time and shortest-duration greedily produce fewer meetings. Read those counterexamples carefully — being able to break the wrong rules is how you build faith in the right one.

Given activities with start/finish times, pick the largest set that don't overlap. The greedy rule: always take the activity that finishes earliest among those still compatible. Sorting by finish time and sweeping is Θ(n log n).

Exchange proof. Let greedy pick activity g (earliest finish) and suppose some optimal set OPT picks a different first activity o. Since g finishes no later than o, replacing o with g in OPT leaves all later activities still compatible (they started after o finished, hence after g finished). The swapped set is the same size and still valid — so greedy's first choice is safe. Induct on the remainder.

pythondef select_activities(activities):
    """activities: list of (start, finish). Return a max non-overlapping subset."""
    chosen = []
    last_finish = float("-inf")
    for start, finish in sorted(activities, key=lambda a: a[1]):  # earliest finish first
        if start >= last_finish:            # compatible with the last chosen
            chosen.append((start, finish))
            last_finish = finish
    return chosen

acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
picked = select_activities(acts)
print("selected", len(picked), "activities:", picked)

selected 4 activities: [(1, 4), (5, 7), (8, 11), (12, 16)]

3 · Interval partitioning — minimum resources advanced

Flip the last problem on its head and it's suddenly a university registrar's nightmare. In activity selection you had one room and turned meetings away. Now nobody gets turned away — every lecture must be scheduled — and instead you're buying rooms. How few rooms can you rent so that no two overlapping lectures ever land in the same one? Rent too many and you waste money; assign carelessly and you'll double-book. This is interval partitioning, and it shows up anywhere a "how many parallel resources do I need?" question hides: exam rooms, CPU cores for overlapping jobs, machines on a factory floor, database connections in a pool.

There's a beautiful lower bound that makes the answer feel inevitable once you see it. Stand at the busiest instant of the day — the moment when the most lectures are running simultaneously. If seven lectures overlap at 10:05 a.m., then at 10:05 you physically need seven rooms; there is no cleverness that fits seven concurrent lectures into six rooms. That peak simultaneous count is called the depth, and it's a floor you cannot go under. The genuinely surprising part — the thing worth proving — is that the depth is also achievable: greedy never needs more rooms than the depth. So the minimum is exactly the maximum overlap, no more and no less.

The greedy that hits that bound: sort by start time; assign each interval to any currently free resource, opening a new one only when none is free. The common mistake here is over-engineering the "which free room?" decision — agonizing over which idle room to reuse. It doesn't matter; any free room works, because a room is free precisely when its last lecture has ended, and all that matters is whether some room is free. A min-heap keyed on end times makes "is any room free?" an O(log n) check (peek the room that frees soonest), giving Θ(n log n) overall. If you find yourself wanting to backtrack and reshuffle assignments, that's the tell you've stopped trusting the greedy-choice property — the whole point is that you never have to.

A dual problem: schedule all intervals using the fewest resources (rooms, machines) so overlapping intervals get different resources. The greedy: sort by start time; assign each interval to any free resource, opening a new one only when none is free. The number of resources equals the maximum overlap ('depth') — and you cannot beat the depth, so greedy is optimal.

pythonimport heapq

def min_rooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])      # by start time
    heap = []                               # end times of rooms in use (min at top)
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)             # a room freed up -> reuse it
        heapq.heappush(heap, end)
    return len(heap)                        # rooms never freed = peak overlap

meetings = [(0, 30), (5, 10), (15, 20)]
print("rooms needed:", min_rooms(meetings))            # 2
print("rooms:", min_rooms([(1, 5), (2, 6), (3, 7), (8, 9)]))  # 3

rooms needed: 2
rooms: 3

4 · Huffman coding — optimal prefix codes expert

This one isn't a textbook toy — it's running billions of times a second inside every zip file, PNG, and JPEG you've ever opened. Here's the problem it solves. If you store text with a fixed 8 bits per character, the letter e (which shows up constantly) costs exactly as much as q (which barely appears). That's obviously wasteful: you're spending the same on your most common symbol and your rarest. The intuition is the same one Morse code got right in 1838 — give the frequent symbols short codes and the rare ones long codes, and the total shrinks. Huffman coding is the algorithm that finds the provably shortest such assignment, and it does it greedily.

But variable-length codes hide a nasty trap you have to design around. If e is 0 and t is 01, then when the decoder reads 01 it can't tell whether that's a t or an e followed by the start of something else. The bitstream becomes ambiguous — unreadable. The fix is the prefix code: no codeword may be a prefix of another. Then the instant the decoder has read a complete codeword it knows it's complete, because nothing longer starts with those bits. Think of phone numbers: if 911 is a complete emergency number, no other number can start with 911, or the operator wouldn't know when you've finished dialing. Prefix-freeness is what makes a stream of glued-together codewords decodable with no separators.

Huffman builds an optimal prefix code (no codeword is a prefix of another) that minimizes total encoded length given symbol frequencies. The greedy move is disarmingly simple: repeatedly merge the two lowest-frequency nodes into a parent whose frequency is their sum, until one tree remains; the path from the root spells each symbol's code. Why the two rarest? Because in a binary tree the deepest leaves get the longest codes, and you want your longest codes spent on your least-frequent symbols — so you push the two rarest to the bottom and let everything more common float up shallower. The common mistake is trying to be clever about it — sorting once and pairing greedily left-to-right, or grouping by some other heuristic — which quietly produces a valid but suboptimal tree. The exact "always the two current-rarest, re-heapified after each merge" discipline is what the proof below requires; deviate and you lose optimality. It runs in Θ(n log n) with a heap and is the backbone of DEFLATE/gzip and JPEG.

Why merging the two rarest is safe. In an optimal tree the two deepest leaves are siblings (else move one up and shorten the code). An exchange argument shows the two lowest-frequency symbols can be made those deepest siblings without increasing cost — so greedily pairing them is optimal, and the rest follows by induction on the merged 'super-symbol'.

pythonimport heapq
from collections import Counter

def huffman_codes(text):
    freq = Counter(text)
    if len(freq) == 1:                      # single-symbol edge case
        return {next(iter(freq)): "0"}
    # nodes as (freq, tie_id, node); node is a symbol str or a (left, right) tuple
    nodes = [(f, i, sym) for i, (sym, f) in enumerate(freq.items())]
    heapq.heapify(nodes)
    counter = len(nodes)
    while len(nodes) > 1:
        f1, _, n1 = heapq.heappop(nodes)    # two rarest
        f2, _, n2 = heapq.heappop(nodes)
        heapq.heappush(nodes, (f1 + f2, counter, (n1, n2)))
        counter += 1
    root = nodes[0][2]

    codes = {}
    def walk(node, prefix):  # noqa
        if isinstance(node, str):
            codes[node] = prefix or "0"
        else:
            walk(node[0], prefix + "0")
            walk(node[1], prefix + "1")
    walk(root, "")
    return codes

text = "abracadabra"
codes = huffman_codes(text)
encoded_bits = sum(len(codes[c]) for c in text)
print("codes:", {k: codes[k] for k in sorted(codes)})
print("Huffman bits:", encoded_bits, "vs fixed 3-bit:", 3 * len(text))

codes: {'a': '0', 'b': '110', 'c': '100', 'd': '101', 'r': '111'}
Huffman bits: 23 vs fixed 3-bit: 33

5 · Fractional knapsack — where greedy beats DP advanced

Imagine you're a gold prospector with one backpack and a cave full of loot. There's gold dust, silver nuggets, a pile of copper — each pile has a total value and a weight, and your pack holds only so many kilos. You want to walk out with the most valuable haul. The magic ingredient in this version of the story is that everything is pourable: if you can't fit the whole pile of gold dust, you scoop in half of it and take half the value. That single word — pourable, divisible, fractional — is what makes this problem greedy-friendly, and it's worth pausing on, because it's the exact hinge that the next section (0/1 knapsack) removes to break greedy.

The right instinct is to rank by value-per-weight — the density, value ÷ weight — and greedily pour in the densest stuff first, topping off the last bit of space with a fraction of whatever's next-densest. Notice this is the same "what am I actually spending?" reframing from activity selection: the scarce resource is weight capacity, so you want the most value per unit of the thing you're rationing. A very common mistake is to sort by raw value instead — grabbing the single most valuable pile first — which can fill your pack with something heavy and mediocre while a lighter, denser pile sits behind. Density, not headline value, is the correct greedy key here.

Unlike 0/1 knapsack, in the fractional version you may take a fraction of an item. Now greedy is optimal: sort by value-per-weight and take as much of the densest item as fits, breaking the last item fractionally. Θ(n log n). The fractionality is what unlocks the exchange argument — any suboptimal packing can be improved by swapping in a denser fraction: if your pack contains any unit of a less-dense item while a denser item is still available, pour out that unit and pour in the denser one, and your total value strictly rises. Because that swap always improves things, no packing that isn't densest-first can be optimal — which is exactly the greedy-choice property, proven. Keep that swap picture in mind, because the moment items become indivisible you'll no longer be able to make it, and that's precisely when greedy dies and DP takes over.

pythondef fractional_knapsack(items, W):
    """items: list of (value, weight). Return max value for capacity W."""
    items = sorted(items, key=lambda it: it[0] / it[1], reverse=True)  # densest first
    total = 0.0
    for value, weight in items:
        if W <= 0:
            break
        take = min(weight, W)               # take a fraction of the last item
        total += value * (take / weight)
        W -= take
    return round(total, 2)

items = [(60, 10), (100, 20), (120, 30)]    # (value, weight)
print("fractional, W=50:", fractional_knapsack(items, 50))   # 240.0
print("fractional, W=25:", fractional_knapsack(items, 25))

fractional, W=50: 240.0
fractional, W=25: 135.0

6 · When greedy FAILS — and DP saves you expert

This is the section that keeps you out of production incidents, so slow down here. Everything so far taught you to trust greedy; this teaches you to distrust it, which is the more valuable skill by far. Return to the prospector. Take away the "pourable" property — now every item is a solid gold bar you must take whole or not at all — and the same density-first greedy that was provably optimal one section ago becomes provably wrong. That's 0/1 knapsack, and the numbers in the lab below are brutal: greedy grabs the densest bar (value 60, weight 10), then the next it can fit, and walks out with 160; the optimal packing skips the densest bar entirely and leaves with 220. Greedy underperforms by a third, silently, on a three-item input.

Here's the everyday version of the trap so it sticks. Greedy failing is like taking the job with the highest starting salary and later discovering it had no room to grow, while the offer you turned down would have doubled in two years. The locally best move (biggest number now) foreclosed the globally best outcome — and because greedy never reconsiders, you can't undo it. The precise tell, the thing to scan for in any problem, is a choice that is irrevocable AND interacts with future choices. Committing to the densest bar is irrevocable (it's in the pack) and it interacts (it eats capacity a better pair needed). When both are true, one greedy commitment can strand you, and no amount of care in later steps repairs an early wrong turn.

The most important skill is knowing when not to be greedy. If a locally optimal choice can foreclose a better global solution, greedy is wrong and you need DP — which is greedy's opposite discipline: instead of committing to one choice, DP tries all choices at each step and keeps the best, paying more time (here Θ(nW) versus greedy's Θ(n log n)) to buy correctness. Two canonical failures anchor this: 0/1 knapsack (taking the densest item first can waste capacity) and min-coin change with non-canonical denominations — the {1,3,4}-make-6 counterexample from §1, where largest-first gives three coins and the optimum is two. The discipline this whole lesson is really teaching: don't reach for DP out of fear and don't reach for greedy out of hope — prove the greedy-choice property, and if you can't, that failure to prove it is itself the signal to use DP.

pythondef greedy_01(items, W):
    items = sorted(items, key=lambda it: it[0] / it[1], reverse=True)
    total, w = 0, 0
    for value, weight in items:
        if w + weight <= W:                 # 0/1: take whole item or none
            total += value; w += weight
    return total

def dp_01(items, W):
    dp = [0] * (W + 1)
    for value, weight in items:
        for cap in range(W, weight - 1, -1):
            dp[cap] = max(dp[cap], value + dp[cap - weight])
    return dp[W]

items = [(60, 10), (100, 20), (120, 30)]    # (value, weight)
W = 50
print("greedy 0/1:", greedy_01(items, W), " DP 0/1:", dp_01(items, W))

greedy 0/1: 160  DP 0/1: 220

Checkpoint expert

pythondef find_content_children(g, s):
    g.sort(); s.sort()
    child = cookie = 0
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:           # this cookie contents this child
            child += 1
        cookie += 1
    return child

print(find_content_children([1, 2, 3], [1, 1]))    # 1
print(find_content_children([1, 2], [1, 2, 3]))    # 2

1
2

pythondef erase_overlap(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[1])      # earliest end first
    kept, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:
            kept += 1; last_end = end
    return len(intervals) - kept

print(erase_overlap([(1, 2), (2, 3), (3, 4), (1, 3)]))   # 1
print(erase_overlap([(1, 2), (1, 2), (1, 2)]))           # 2
print(erase_overlap([(1, 2), (2, 3)]))                   # 0

1
2
0

pythondef can_jump(nums):
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:                    # unreachable gap
            return False
        farthest = max(farthest, i + jump)
    return True

print(can_jump([2, 3, 1, 1, 4]))   # True
print(can_jump([3, 2, 1, 0, 4]))   # False
print(can_jump([0]))               # True (already at end)

True
False
True

pythondef min_jumps(nums):
    jumps = cur_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:                    # must jump now to go further
            jumps += 1
            cur_end = farthest
    return jumps

print(min_jumps([2, 3, 1, 1, 4]))          # 2
print(min_jumps([2, 3, 0, 1, 4]))          # 2
print(min_jumps([1, 1, 1, 1]))             # 3

2
2
3

pythonimport heapq
from collections import Counter, deque

def least_interval(tasks, n):
    counts = Counter(tasks)
    heap = [-c for c in counts.values()]    # max-heap via negation
    heapq.heapify(heap)
    time = 0
    cooldown = deque()                      # (ready_time, remaining_count)
    while heap or cooldown:
        time += 1
        if heap:
            remaining = heapq.heappop(heap) + 1   # ran one instance
            if remaining < 0:
                cooldown.append((time + n, remaining))
        if cooldown and cooldown[0][0] == time:
            heapq.heappush(heap, cooldown.popleft()[1])
    return time

print(least_interval(["A","A","A","B","B","B"], 2))   # 8
print(least_interval(["A","A","A","B","B","B"], 0))   # 6
print(least_interval(["A","A","A","A","B","C"], 2))   # 10

8
6
10

pythondef can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1                           # not enough fuel overall
    start = 0
    tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                        # can't reach i+1 from `start`
            start = i + 1                   # ...nor from anything in between
            tank = 0
    return start

print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))   # 3
print(can_complete_circuit([2, 3, 4], [3, 4, 3]))               # -1
print(can_complete_circuit([5, 1, 2, 3, 4], [4, 4, 1, 5, 1]))   # 4

3
-1
4