Greedy algorithms

A greedy algorithm is a claim, not a technique: the claim that a local choice is part of some global optimum. This guide is organised around proving that claim — the greedy-choice property, the exchange argument that establishes it, and the fact that a wrong greedy rule fails silently with a valid but suboptimal answer rather than an error. It works through the problems where greedy is provably right (interval scheduling by finish time, fractional knapsack by density, Huffman coding, minimum spanning trees via the cut property, Dijkstra under non-negative weights) and the ones where it is provably wrong, and it treats approximation ratios and online competitive ratios as results in their own right rather than as consolation prizes.

what makes a greedy algorithm correct

A greedy algorithm is correct only when a locally optimal choice is provably part of some globally optimal solution.

The proof is usually an exchange argument: take any optimal solution, swap in the greedy choice, and show the result is no worse.

An exchange argument, or it is a guess.

# Claim: taking the interval that finishes earliest is safe.
# Proof: let OPT be optimal and f the earliest-finishing interval. If OPT lacks f,
# swap OPT's first interval for f. f finishes no later, so the rest of OPT still fits.
# |OPT| is unchanged. Therefore some optimal solution contains f.

Interview trap. Believing a greedy rule because it works on the examples is the single most common error, and the counterexample is often small.

Engineering practice. State the exchange argument before writing the code, and if you cannot, treat the problem as dynamic programming instead.

the greedy-choice property

The greedy-choice property says the first decision can be made without considering the subproblems it creates.

This is stronger than optimal substructure, which dynamic programming also needs; greedy additionally requires the choice to be safe in isolation.

Optimal substructure is not enough; knapsack has it and greedy still fails.

# Items (value, weight): (60, 10), (100, 20), (120, 30); capacity 50.
# Greedy by density: 60 + 100 = 160, 20 units left, item 3 does not fit.
# Optimal: 100 + 120 = 220.

Interview trap. Conflating the two properties leads to greedy solutions for problems that only have optimal substructure, such as the zero-one knapsack.

Engineering practice. Check both properties separately, and name which one fails when greedy does.

the exchange argument

An exchange argument proves greedy correctness by transforming any optimal solution into the greedy one without losing quality.

It shows that if an optimal solution differs from the greedy choice, swapping in the greedy choice yields another solution at least as good.

Take any optimum, find the first difference, exchange, show no loss.

# Structure of the proof:
#   1. Let OPT be any optimal solution.
#   2. Let g be the greedy choice, and suppose OPT does not contain it.
#   3. Construct OPT' by swapping g in; show OPT' is feasible and no worse.
#   4. Therefore an optimal solution containing g exists. Induct.

Interview trap. An argument that only shows the greedy solution is good, without comparing it to an arbitrary optimum, proves nothing.

Engineering practice. Structure the argument as 'take any optimum, find the first difference, exchange, and show no loss'.

interval scheduling

Selecting the maximum number of non-overlapping intervals is solved by always taking the interval that finishes earliest.

Finishing earliest leaves the most room for the remaining intervals, which is exactly what the exchange argument formalises.

Sort by end time; start time and duration both fail.

intervals.sort(key=lambda x: x[1])       # by finish
count, last_end = 0, float("-inf")
for s, e in intervals:
    if s >= last_end: count += 1; last_end = e

# [(0,10), (1,2), (3,4)]: by start -> 1; by end -> 2.

Interview trap. Sorting by start time or by duration both fail, and a single three-interval counterexample defeats each.

Engineering practice. Sort by end time, and be ready to give the counterexample that defeats the alternative orderings.

interval partitioning

The minimum number of resources needed for overlapping intervals equals the maximum number overlapping at any instant.

Sweeping endpoints and tracking the running count gives the number; processing starts with a heap of resource end times additionally constructs an assignment.

Rooms needed equals peak overlap, not total duration.

events = sorted([(s, 1) for s, _ in iv] + [(e, -1) for _, e in iv])
cur = peak = 0
for _, delta in events:
    cur += delta; peak = max(peak, cur)

# Three 1-hour meetings back to back need 1 room; three overlapping need 3.

Interview trap. Assuming the answer relates to the total duration rather than the peak concurrency gives a number unrelated to the constraint.

Engineering practice. Sweep the events, and note that the peak overlap is a lower bound the greedy assignment achieves exactly.

fractional versus zero-one knapsack

The fractional knapsack is greedy by value density; the zero-one knapsack is not greedy at all.

Fractional items can fill the capacity exactly, which is what makes the density ordering safe; indivisible items leave a remainder that the ordering cannot account for.

Divisibility is what makes the density rule safe.

# Same items as above, capacity 50, but divisible:
# 60 + 100 + (2/3) x 120 = 240 - greedy by value/weight is optimal.

Interview trap. Applying the density rule to indivisible items gives a plausible answer that is provably suboptimal on small instances.

Engineering practice. Check divisibility first, and use dynamic programming for the indivisible case.

coin change and canonical systems

Greedy coin change is correct for some coin systems and wrong for others, so correctness depends on the denominations rather than on the algorithm.

A system is called canonical when the greedy result is always optimal, and deciding canonicity is itself a non-trivial computation.

Denominations decide correctness, not the algorithm.

# [1, 5, 10, 25] target 30 -> greedy 25 + 5 = 2 coins  (optimal)
# [1, 3, 4]      target 6  -> greedy 4 + 1 + 1 = 3     (optimal is 3 + 3 = 2)

Interview trap. Assuming greedy works because it does for common currency systems fails on systems where a middle denomination blocks the optimum.

Engineering practice. Use dynamic programming unless the coin system is known canonical, and state that assumption explicitly.

the jump-game reachability rule

Deciding whether the end of an array is reachable is greedy: track the furthest position reachable so far and fail when the current index passes it.

The furthest reachable position is monotone, so a single pass suffices with no search over jump choices.

Track the furthest reach; it is monotone.

reach = 0
for i, jump in enumerate(a):
    if i > reach: return False
    reach = max(reach, i + jump)
return True

# [2, 3, 1, 1, 4] -> True; [3, 2, 1, 0, 4] -> False

Interview trap. Searching over all jump sequences is exponential and unnecessary, and a dynamic program is quadratic where the greedy is linear.

Engineering practice. Maintain the running maximum reach, and note the linear bound against the quadratic alternative.

minimum jumps

Counting the minimum jumps is greedy by levels: each jump extends to the furthest position reachable from the current level.

The structure is exactly a breadth-first search on an implicit graph, where a level is the set of positions reachable in the same number of jumps.

Levels, like a BFS on an implicit graph.

if len(a) < 2: return 0
jumps = end = far = 0
for i in range(len(a) - 1):
    far = max(far, i + a[i])
    if i == end:
        if far == end: return -1             # the next level is unreachable
        jumps += 1; end = far                # crossed the level boundary
        if end >= len(a) - 1: return jumps
return -1

# [2, 3, 1, 1, 4] -> 2; [0, 1] -> -1

Interview trap. Jumping to the position with the largest single value rather than the largest reach is a different and incorrect rule.

Engineering practice. Track the current level's boundary and the furthest reach, and increment the count when the boundary is crossed.

Huffman coding

Huffman's algorithm builds an optimal prefix code by repeatedly merging the two least frequent symbols.

The exchange argument shows the two rarest symbols can always be siblings at the deepest level of some optimal tree.

Merge the two rarest repeatedly; ranking by frequency alone is not the same.

import heapq
h = [(f, i, None) for i, f in enumerate(freqs)]
heapq.heapify(h)
while len(h) > 1:
    a = heapq.heappop(h); b = heapq.heappop(h)
    heapq.heappush(h, (a[0] + b[0], next(seq), (a, b)))

# Frequencies 5, 9, 12, 13, 16, 45 -> 224 bits, against 3 x 100 = 300 for fixed-length.

Interview trap. Assigning code lengths by frequency rank rather than by the merge tree does not produce an optimal code.

Engineering practice. Use a priority queue over the merge frequencies, and note that optimality is over prefix codes with the given symbol frequencies.

greedy in minimum spanning trees

Both Kruskal and Prim are greedy, and their correctness rests on the cut property rather than on intuition.

The cut property states that the lightest edge crossing any partition belongs to some minimum spanning tree, which licenses each greedy addition.

The cut property is the licence for each addition.

# Any partition of the vertices: the lightest edge crossing it is in some MST.
# Kruskal takes globally lightest edges that join two components;
# Prim takes the lightest edge leaving the grown component. Same property, two orders.

Interview trap. Assuming greedy works for spanning trees but not shortest paths, or the reverse, misses that each has its own proof.

Engineering practice. Cite the cut property when defending the spanning-tree algorithms, and the non-negativity assumption when defending Dijkstra.

Dijkstra as a greedy algorithm

Dijkstra is greedy: it finalises the nearest unfinalised vertex, and that is safe only because edge weights are non-negative.

A negative edge could make a longer-looking route cheaper later, which breaks the safety of finalising early.

Finalising the nearest vertex is safe only with non-negative weights.

# A -> B = 2, A -> C = 5, C -> B = -4
# Dijkstra finalises B at 2; the true shortest is A -> C -> B = 1.

Interview trap. Presenting Dijkstra as universally correct for weighted graphs omits precisely the assumption its greedy step depends on.

Engineering practice. State the non-negativity requirement whenever the algorithm is proposed.

sorting as the greedy preprocessing step

Most greedy algorithms are a sort followed by a linear pass, so the complexity is usually dominated by the sort.

The sort key encodes the greedy rule, which means choosing the key correctly is the entire design decision.

The sort dominates; quote O(n log n).

intervals.sort(key=lambda x: x[1])    # O(n log n) - the real cost
for s, e in intervals: ...            # O(n)

Interview trap. Reporting the greedy pass as linear ignores the sort that made it possible.

Engineering practice. Quote the total as O(n log n), and name the sort key as the rule being applied.

sorting by a composite key

When the greedy rule involves two attributes, the sort key must combine them in the order the rule requires.

Sorting by one attribute and tie-breaking by another expresses a different rule from sorting by their ratio or difference.

Derive the comparison from the exchange argument, including ties.

# Scheduling to minimise total weighted completion time: sort by ratio, not by
# either field alone.
jobs.sort(key=lambda j: j.time / j.weight)

Interview trap. Choosing the composite key by intuition rather than from the exchange argument produces a rule that fails on ties.

Engineering practice. Derive the comparison from the exchange argument, including what happens when two items compare equal.

greedy with a heap

When the greedy choice depends on state that changes as the algorithm proceeds, a priority queue replaces the initial sort.

Task scheduling with deadlines and cooldowns both need the current best choice rather than a fixed order, which is what the heap provides.

When the ranking changes during the run, pre-sorting applies a stale rule.

import heapq
# Task scheduler with cooldown: the best next task depends on which are cooling down,
# which changes every tick - so the choice comes from a heap, not from a fixed order.

Interview trap. Pre-sorting when the rule depends on evolving state applies the rule to stale information.

Engineering practice. Ask whether the ranking changes during the run; if it does, use a heap rather than a sort.

gas-station and circular reasoning

The circular-route problem is greedy: if the total surplus is non-negative a solution exists, and the start is the position after the lowest running prefix.

Any prefix that goes negative rules out every start within it, so the search never needs to restart from an interior position.

Total decides feasibility; the running deficit decides the start.

total = tank = start = 0
for i, (gas, cost) in enumerate(stations):
    total += gas - cost; tank += gas - cost
    if tank < 0: start, tank = i + 1, 0      # every earlier start is ruled out
return start if total >= 0 else -1

Interview trap. Testing every start point is quadratic and unnecessary, and stopping at the first failure without resetting the start gives a wrong answer.

Engineering practice. Track the total and the running deficit separately, and justify skipping the eliminated starts.

proving impossibility

A greedy algorithm often needs a separate feasibility check, because the greedy pass alone cannot distinguish 'no solution' from 'this solution'.

In the circular-route case the total surplus decides feasibility, which the greedy scan does not compute on its own.

The greedy scan alone cannot tell 'no solution' from 'this solution'.

return start if total >= 0 else -1      # the feasibility check is separate

Interview trap. Returning the greedy candidate without the feasibility check reports a start position for an infeasible instance.

Engineering practice. Separate feasibility from construction, and compute both.

when greedy is an approximation

For many NP-hard problems greedy gives a provable approximation ratio rather than an optimum, and the ratio is the result.

Greedy set cover achieves a logarithmic approximation ratio, which is essentially the best possible under standard complexity assumptions.

Set cover: greedy is ln(n)-approximate, and that is essentially optimal.

# Universe of 1,000 elements: greedy uses at most ~7x the optimal number of sets.
# Under standard complexity assumptions no polynomial algorithm does better.

Interview trap. Presenting an approximation as an optimum, or a heuristic with no proven ratio as an approximation, misrepresents the guarantee.

Engineering practice. State the ratio and its proof source, or say plainly that the rule is a heuristic without a bound.

greedy versus dynamic programming

Greedy is faster and applies less often; dynamic programming applies whenever there is optimal substructure, with or without the greedy-choice property.

The practical procedure is to attempt the exchange argument first and fall back to a recurrence when it fails.

Try the exchange argument first; fall back to a recurrence.

Problem	Greedy	DP
Fractional knapsack	optimal	unnecessary
Zero-one knapsack	wrong	optimal
Interval scheduling	optimal	unnecessary
Coin change, arbitrary coins	wrong	optimal

Interview trap. Choosing greedy for speed without the proof trades a correct slow answer for a fast wrong one.

Engineering practice. Default to the dynamic program when the proof is unavailable, and note the greedy alternative as a possible optimisation.

finding counterexamples

The fastest way to falsify a candidate greedy rule is to compare small random instances with exhaustive enumeration, but passing those checks is not a proof.

Counterexamples to wrong greedy rules are often tiny, so brute force finds defects quickly; only an exchange argument or equivalent proof establishes correctness for every input.

Random tiny instances against brute force, in seconds.

for _ in range(20_000):
    a = [random.randint(1, 9) for _ in range(random.randint(1, 6))]
    assert my_greedy(a) == brute_force(a), a

This can disprove a rule in seconds; a clean run still needs an exchange argument.

Interview trap. Treating a large random test run as proof confuses failure to find a counterexample with evidence that none exists.

Engineering practice. Use brute force to hunt for counterexamples, then supply the proof before committing to the rule.

stability of the greedy order

When several items compare equal under the greedy key, the result may depend on their relative order, which must be either irrelevant or specified.

A stable sort preserves the input order among equals, which makes the algorithm deterministic even when the rule does not decide.

Ties must be either irrelevant or explicitly broken.

items.sort(key=lambda x: (x.ratio, x.id))     # deterministic among equals
# Python's sort is stable, so key ties preserve input order - a guarantee worth stating.

Interview trap. Relying on an unstable sort's tie order produces results that change between library versions or input sizes.

Engineering practice. Use a stable sort or add an explicit tiebreaker, and say whether ties affect the answer's value or only its form.

greedy in scheduling systems

Production schedulers are greedy by construction, because a decision must be made when work arrives rather than after all work is known.

Online algorithms are evaluated by competitive ratio against an offline optimum that has full knowledge in advance.

Online: measure competitive ratio, not optimality.

# List scheduling on m machines is (2 - 1/m)-competitive against the offline optimum.
# An online scheduler that is 20% off the offline optimum may be doing very well.

Interview trap. Comparing an online scheduler against an offline optimum without acknowledging the information gap misattributes the shortfall to the algorithm.

Engineering practice. State whether the setting is online or offline, and use competitive ratio rather than optimality as the criterion online.

local optima and hill climbing

A greedy rule that always improves the current solution finds a local optimum, which is not the same as a global one.

Escaping a local optimum needs a mechanism such as restarts, simulated annealing, or a lookahead that greedy by definition lacks.

Improving every step finds a local optimum, not a global one.

# 2-opt on a TSP tour improves until no single swap helps.
# That is a local optimum; restarts or annealing are what escape it.

Interview trap. Describing hill climbing as greedy is fair, but describing its result as optimal is not.

Engineering practice. Say local optimum when that is what the algorithm finds, and describe the escape mechanism if one is used.

the cost of a wrong greedy rule

A wrong greedy algorithm fails silently, producing a valid but suboptimal answer with no error condition.

This makes greedy defects unusually expensive: they pass tests that check validity and only show up as a persistent quality gap.

Valid output, silently suboptimal, no error anywhere.

assert is_valid(result)                # passes for a wrong greedy rule
assert cost(result) == cost(optimal)   # the check that actually catches it

Interview trap. Validating only that the output satisfies the constraints does not detect suboptimality at all.

Engineering practice. Compare against the optimum on small instances, and monitor solution quality against a bound in production.

recognising a greedy problem

Greedy fits when a single ordering makes each choice obviously safe, and the ordering is usually about what leaves the most room for the rest.

Earliest finish time, largest value density, smallest remaining deadline, and least frequency all share that shape.

Order by what leaves the most room for the rest.

Problem	Ordering
Maximum non-overlapping intervals	earliest finish
Fractional knapsack	highest value density
Huffman coding	lowest frequency first
Minimum spanning tree	lightest crossing edge

Interview trap. Choosing the ordering that seems most natural rather than the one the exchange argument supports is how greedy solutions go wrong.

Engineering practice. Ask what quantity the choice should preserve for the remaining problem, and order by that.