Algorithm design · 33 / 53
Greedy: when are local choices correct?
Understand → trace → implement → justify
1 min reading · allow extra time for practiceGreedy chooses a locally best step, but correctness needs a proof such as an exchange argument: replace the first choice of an optimum with the greedy choice without worsening it, then repeat.
Earliest-finish-time interval scheduling maximises the number of compatible intervals. Earliest-start or shortest-duration choices do not share that guarantee. Weighted interval scheduling changes the objective and requires DP.
Coin greedy fails for denominations [1,3,4] and target6:4+1+1 loses to3+3. Fractional knapsack allows value/weight ratios; indivisible0/1 knapsack does not. Matroids formalise important families where greedy is optimal.
A worked trace
Intervals [0,3),[1,2),[2,4): earliest finish chooses [1,2) then[2,4), giving two instead of one.
Cost and assumptions
Sorting O(n log n), scan O(n). Proof depends on objective and interval boundaries.
Executable example
Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.
def schedule(intervals):
chosen, end = [], float("-inf")
for start, finish in sorted(intervals, key=lambda x:x[1]):
if start >= end:
chosen.append((start,finish)); end=finish
return chosen
assert len(schedule([(0,3),(1,2),(2,4)])) == 2TEST YOUR UNDERSTANDING
Your turn
How would you fix coin greedy missing3+3?
Reveal the reasoning
Use DP for general denominations: dp[x]=1+min dp[x−coin], with dp[0]=0 and infinity for unreachable sums.
Take it further
- Write down the input contract and the invariant before changing the example.
- Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
- Derive the cost under the stated model; measure several input sizes and explain discrepancies.
Primary reading & lecture notes
Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.
Jeff Erickson · Algorithms ↗