Greedy Algorithms
A greedy algorithm makes the locally optimal choice at each step, hoping that these local choices lead to a globally optimal solution. Unlike dynamic programming, which considers all possible subproblems, a greedy algorithm commits to a choice and never looks back. When the problem has the right structure, this one-directional strategy produces optimal results in a fraction of the time DP would take.
The catch: greedy does not always work. Knowing when it works and when it fails is the real skill.
This is the Module 5 lesson on greedy algorithms in DSA: Zero to Mastery. It assumes you can sort with a custom key, use a heap, and follow a proof by induction (Recursion & Induction). You have already met greedy ideas in Intervals and Minimum Spanning Trees; this lesson explains why they work, gives you four proof techniques, and shows you how to break a greedy idea with a counterexample before an interviewer does.
Why this exists
Many optimisation problems ask you to pick a subset or an order: which meetings to accept, which jobs to run first, which edges to keep, which bits to give to which letters. Trying every subset costs ; trying every order costs . For that is a billion subsets or orders. Dynamic programming often cuts that down to a polynomial, but it still looks at every subproblem.
A greedy algorithm goes further: it decides one piece of the answer by a simple rule ("the meeting that ends first", "the two rarest letters", "the cheapest edge"), never undoes it, and moves on. That usually means "sort once, then scan", which is — or a single pass, . When it is correct, it is the fastest and simplest algorithm there is.
The ideas are old. Kruskal (1956) and Prim (1957) gave greedy minimum spanning tree algorithms; Borůvka had one in 1926. David Huffman found his optimal coding algorithm as an MIT graduate student in 1951–52, in a term paper he chose instead of a final exam (Huffman, 1952). Jackson's 1955 "earliest due date" rule for scheduling is a greedy algorithm. In 1971 Jack Edmonds explained a large family of these successes at once with matroids: greedy is optimal on every matroid, and only there (for the "pick a best subset" form of the problem). You will see all of these below.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "maximum number of non-overlapping intervals / meetings / movies" | Sort by finish time, take each one that fits (activity selection) |
| "minimum rooms / platforms / machines so nothing overlaps" | Sort by start, min-heap of end times; answer = maximum depth |
| "minimum arrows / points to hit all intervals" | Sort by finish, shoot at the finish of the first un-hit interval |
| "minimise the maximum lateness", deadlines with durations | Earliest deadline first (EDF) |
| "minimise total (or average) completion time" | Shortest job first |
| "optimal prefix code", "merge files / ropes / sticks with cost = sum of sizes" | Huffman: repeatedly merge the two smallest (min-heap) |
| "take fractions of items" | Fractional knapsack: best value per weight first |
| "minimum cost to connect everything" | MST: Kruskal or Prim |
| "can you reach the end?", "minimum jumps" | Track the farthest reachable index (jump game I and II) |
| "circular route, fuel, can you complete the loop?" | Gas station: one pass, reset the start when the tank goes negative |
| "each child gets more than a neighbour with a higher rating" | Two passes, left-to-right and right-to-left (candy) |
| "send exactly half to A and half to B, minimise cost" | Sort by the difference (two-city scheduling) |
| "same task needs a cool-down of " | Count-based formula around the most frequent task |
| Values with a weight and you must take whole items | Probably not greedy: 0/1 knapsack is DP |
| Arbitrary coin denominations, "fewest coins" | Probably not greedy: test with 6 |
The meta-trigger: there is an obvious "best next move", and taking it never seems to close a door you would want later. Your job is to check the second half of that sentence — with a proof or a counterexample.
Intuition & first principles
Commit, and never look back
Picture a cashier giving change for 63 cents with US coins (25, 10, 5, 1). They grab the biggest coin that fits, again and again: 25, 25, 10, 1, 1, 1 — six coins. Nobody makes 63 with fewer. The cashier never considered "what if I took a 10 first?" They committed, and it worked.
Now give the same cashier coins of 1, 3 and 4 and ask for 6. Biggest first gives 4, 1, 1 — three coins. But 3 + 3 is two coins. The first choice (4) looked best and quietly ruined the rest. Same algorithm, different input structure, wrong answer.
That is the whole subject in two examples. A greedy algorithm is:
- A rule that picks the next piece of the answer, using only what is in front of it.
- A commitment: the piece is never removed later.
- A shrink: after the choice, what is left is a smaller problem of the same kind.
The algorithm is correct when step 1 never picks something that every optimal answer avoids. Proving that is the only hard part.
Words we will use
- Feasible solution: any answer that obeys the rules (for example, a set of meetings with no overlaps).
- Optimal solution: a feasible solution with the best possible value. There may be several.
- Greedy choice: the piece the rule picks first.
- Greedy choice property: some optimal solution contains the greedy choice. (Not every one — just one.)
- Optimal substructure: once the greedy choice is made, an optimal answer to the remaining smaller problem, plus the greedy choice, is optimal for the whole problem.
- Counterexample: a specific small input on which the rule gives a worse answer than the best one. One counterexample kills a greedy rule for good.
A tiny example you can hold in your head
Three talks, one room. Talk P runs 9:00–12:00, Q runs 9:30–10:00, R runs 10:00–10:30. Which talks should the room host to fit the most?
- "Earliest start first" picks P (9:00) and then nothing else fits: 1 talk.
- "Earliest finish first" picks Q (ends 10:00), then R (starts 10:00, fits): 2 talks.
Why does "finishes first" work? Whatever you pick first, the rest of the day after it finishes is what you have left to fill. The talk that finishes first leaves the most day behind. Any other first pick leaves the same or less. That one sentence is the seed of the exchange argument we prove carefully below.
The Two Properties
A problem is amenable to a greedy approach when it has both:
1. Greedy Choice Property
A globally optimal solution can be assembled by making locally optimal (greedy) choices. You can prove this by showing that any solution can be modified to include the greedy choice without worsening it (an "exchange argument").
2. Optimal Substructure
An optimal solution to the problem contains optimal solutions to its subproblems. This property is shared with dynamic programming — the difference is that greedy problems also satisfy the greedy choice property, so you only need to solve one subproblem at each step instead of all of them.
graph TD
A["Problem has optimal substructure?"] -->|Yes| B["Greedy choice property holds?"]
A -->|No| C["Neither DP nor Greedy<br/>Try other approaches"]
B -->|Yes| D["Use Greedy<br/>O(n log n) typical"]
B -->|No| E["Use DP<br/>O(n * states) typical"]
style D fill:#4caf50,color:#fff
style E fill:#2196f3,color:#fff
style C fill:#f44336,color:#fff
The Greedy Template
Most greedy algorithms follow this pattern:
- Sort or otherwise order the input by some criterion
- Iterate through the sorted input
- Greedily select each element if it is compatible with previous choices
- Return the accumulated result
TypeScript:
function greedyTemplate<T>(
items: T[],
comparator: (a: T, b: T) => number,
isCompatible: (selected: T[], candidate: T) => boolean
): T[] {
const sorted = [...items].sort(comparator);
const result: T[] = [];
for (const item of sorted) {
if (isCompatible(result, item)) {
result.push(item);
}
}
return result;
}
Python:
from typing import TypeVar, Callable
T = TypeVar('T')
def greedy_template(
items: list[T],
key: Callable[[T], any],
is_compatible: Callable[[list[T], T], bool]
) -> list[T]:
sorted_items = sorted(items, key=key)
result: list[T] = []
for item in sorted_items:
if is_compatible(result, item):
result.append(item)
return result
Activity Selection (Interval Scheduling)
Problem: Given activities with start and finish times, select the maximum number of non-overlapping activities.
Greedy strategy: Always pick the activity that finishes earliest. This leaves the most room for subsequent activities.
Proof Sketch (Exchange Argument)
Let be an optimal solution and let be the activity with the earliest finish time. If , done. If , let be the first activity in (by finish time). Since finishes no later than , we can replace with without creating conflicts. The resulting set is still optimal and includes the greedy choice.
TypeScript:
interface Activity {
start: number;
finish: number;
name: string;
}
function activitySelection(activities: Activity[]): Activity[] {
// Sort by finish time
const sorted = [...activities].sort((a, b) => a.finish - b.finish);
const selected: Activity[] = [sorted[0]];
let lastFinish = sorted[0].finish;
for (let i = 1; i < sorted.length; i++) {
if (sorted[i].start >= lastFinish) {
selected.push(sorted[i]);
lastFinish = sorted[i].finish;
}
}
return selected;
}
// Example
const activities: Activity[] = [
{ start: 1, finish: 4, name: "A" },
{ start: 3, finish: 5, name: "B" },
{ start: 0, finish: 6, name: "C" },
{ start: 5, finish: 7, name: "D" },
{ start: 3, finish: 9, name: "E" },
{ start: 5, finish: 9, name: "F" },
{ start: 6, finish: 10, name: "G" },
{ start: 8, finish: 11, name: "H" },
];
// Result: A, D, H (3 activities)
Python:
from dataclasses import dataclass
@dataclass
class Activity:
start: int
finish: int
name: str
def activity_selection(activities: list[Activity]) -> list[Activity]:
sorted_acts = sorted(activities, key=lambda a: a.finish)
selected = [sorted_acts[0]]
last_finish = sorted_acts[0].finish
for act in sorted_acts[1:]:
if act.start >= last_finish:
selected.append(act)
last_finish = act.finish
return selected
| Metric | Value |
|---|---|
| Time Complexity | for sorting |
| Space Complexity | for sorted copy |
| Greedy Criterion | Earliest finish time |
Trace table
The same eight activities, already sorted by finish time. last is the finish time of the most recently chosen activity; an activity is taken when its start is at least last. (Intervals are half-open, , so one may start exactly when the previous one ends.)
| Step | Activity | Start | Finish | last before | Start ≥ last? | Action | last after |
|---|---|---|---|---|---|---|---|
| 1 | A | 1 | 4 | yes | take | 4 | |
| 2 | B | 3 | 5 | 4 | no (3 < 4) | skip | 4 |
| 3 | C | 0 | 6 | 4 | no | skip | 4 |
| 4 | D | 5 | 7 | 4 | yes | take | 7 |
| 5 | E | 3 | 9 | 7 | no | skip | 7 |
| 6 | F | 5 | 9 | 7 | no | skip | 7 |
| 7 | G | 6 | 10 | 7 | no | skip | 7 |
| 8 | H | 8 | 11 | 7 | yes | take | 11 |
Result {A, D, H}. A brute force over all subsets confirms 3 is the maximum, and the same check on 2,000 random instances of up to 8 intervals never found a case where earliest-finish lost (script run for this lesson).
gantt
title Activities sorted by finish, chosen ones marked active
dateFormat X
axisFormat %s
section Chosen
A :active, 1, 4
D :active, 5, 7
H :active, 8, 11
section Skipped
B : 3, 5
C : 0, 6
E : 3, 9
F : 5, 9
G : 6, 10
Three tempting rules that fail
Earliest finish is not the only "obvious" rule. Each of these sounds reasonable and each is wrong; the counterexamples were checked against brute force.
| Rule | Counterexample (half-open intervals) | Rule picks | Optimum |
|---|---|---|---|
| Earliest start | only → 1 | → 2 | |
| Shortest duration | only (it overlaps both others) → 1 | → 2 | |
| Fewest conflicts | , three copies of , one , three copies of | first (only 2 conflicts), then one interval from each side → 3 | the four on the top row → 4 |
The third one is the classic from Kleinberg and Tardos (§4.1): has the fewest conflicts, but choosing it kills two members of the only 4-element solution.
How to prove a greedy algorithm correct
"It worked on the examples" is not a proof: every rule in the table above works on some examples. There are four standard techniques. The first two do almost all of the work in interviews and contests.
flowchart TD
Q["Candidate greedy rule"] --> T{"Try small counterexamples first"}
T -->|"found one"| X["Rule is wrong: switch to DP or search"]
T -->|"none found"| P{"Which proof fits?"}
P -->|"answer is a set or an order"| EX["Exchange argument"]
P -->|"answer is built step by step"| SA["Greedy stays ahead"]
P -->|"answer is a count of resources"| SB["Structural bound: matching lower bound"]
P -->|"choosing edges or independent sets"| MT["Cut property or matroid"]
Technique 1: the exchange argument
Idea: take any optimal solution . If it disagrees with the greedy solution , swap a piece of for the corresponding piece of , and show the result is still feasible and no worse. Repeat until has become . Then is no worse than an optimal solution, so it is optimal.
Fully worked: activity selection
Setup. Activities with half-open intervals , sorted so . Two activities are compatible if their intervals do not overlap. Greedy takes activity 1, deletes everything that overlaps it, and repeats on what is left.
Lemma (greedy choice). Some maximum-size compatible set contains activity 1.
Proof. Let be any maximum-size compatible set. List it by finish time: . If activity 1 is in we are done. Otherwise build .
- has the same size : we removed one activity and added one that was not there.
- is compatible. Every other () starts at or after , because and are compatible and finishes first. And because activity 1 has the smallest finish time of all. So every starts at or after : none of them overlaps activity 1.
So is a maximum-size compatible set containing activity 1.
Lemma (optimal substructure). Let be the activities that start at or after . If is a maximum compatible subset of , then is a maximum compatible subset of all activities.
Proof. By the first lemma some optimal contains 1. Everything else in is compatible with 1, so it lies in ; thus , i.e. . And is feasible.
Theorem. The greedy algorithm returns a maximum compatible set.
Proof by strong induction on . With the empty set is optimal. Otherwise greedy takes activity 1 and then runs on , which has fewer activities; by induction it returns an optimal for , and by the second lemma is optimal.
This is exactly the shape of every exchange-argument proof: (1) swap to show the greedy choice is safe, (2) show what remains is the same problem, (3) induct.
Fully worked: scheduling to minimise maximum lateness
Problem. One machine, jobs. Job needs time units and has deadline . You run the jobs one after another from time 0, without gaps. If job finishes at time , its lateness is . Minimise the maximum lateness .
Greedy rule: earliest deadline first (EDF). Sort jobs by deadline and run them in that order (Jackson, 1955).
Worked example (the instance from Kleinberg and Tardos §4.2):
| Job | Start | Finish | Lateness | ||
|---|---|---|---|---|---|
| 1 | 3 | 6 | 0 | 3 | 0 |
| 2 | 2 | 8 | 3 | 5 | 0 |
| 3 | 1 | 9 | 5 | 6 | 0 |
| 4 | 4 | 9 | 6 | 10 | 1 |
| 5 | 3 | 14 | 10 | 13 | 0 |
| 6 | 2 | 15 | 13 | 15 | 0 |
Maximum lateness 1. Brute force over all orders confirms 1 is optimal. "Shortest job first" gives maximum lateness 6 on the same input; "smallest slack first" happens to give 1 here but fails on two jobs with , : slack order runs the 10-unit job first and is 9 late, EDF is 1 late.
Proof. Call a pair of jobs an inversion if runs before but . EDF is exactly the schedule with no inversions (ties in deadline can be ordered either way).
- All schedules with no inversions and no idle time have the same maximum lateness. They differ only in the order of jobs with equal deadlines. Those jobs occupy the same block of time in every such schedule, and the last of them finishes at the end of the block, so the worst lateness among them, (block end) , is the same.
- If a schedule has an inversion, it has one between two adjacent jobs. Walk along the schedule: if deadlines never decreased between neighbours, they would never decrease at all.
- Swapping an adjacent inverted pair ( just before , ) does not increase the maximum lateness. Every other job finishes at the same time as before. After the swap, finishes earlier, so its lateness cannot grow. now finishes at time , the time used to finish. Its new lateness is , which was 's old lateness. So the new lateness of is at most the old maximum.
- Each swap removes exactly one inversion, and there are at most , so after finitely many swaps an optimal schedule becomes an inversion-free schedule with no larger maximum lateness. By (1) EDF has the same maximum lateness as it. So EDF is optimal.
The same "fix adjacent inversions" pattern proves shortest-job-first for minimising total completion time, Smith's ratio rule for weighted completion time (sort by ), and two-city scheduling below.
Technique 2: greedy stays ahead
Idea: compare greedy and an optimal solution step by step, and show by induction that after each step greedy is at least as far along by some measure. At the end, being "ahead" means being at least as good.
Fully worked: activity selection again
Let greedy choose and let an optimal solution be , both listed by finish time. We want .
Claim. For every , — greedy's -th activity finishes no later than the optimum's -th.
Proof by induction on . For , greedy picks the earliest finish of all, so . For , assume . Since is compatible with , . So was still available when greedy chose its -th activity, and greedy picks the earliest-finishing available one: .
Theorem. . Proof. Suppose . By the claim , so was still available after greedy's last pick — but greedy only stops when nothing is available. Contradiction.
Stays-ahead proofs are natural when the answer is built in rounds: jump game II (after jumps, greedy reaches at least as far as any strategy), Dijkstra (each settled vertex has its true distance — see Shortest Paths), and the "fewest refuelling stops" problem.
Technique 3: structural bound
Idea: find a simple reason why every solution needs at least of something, then show greedy uses exactly . You never compare against an optimal solution directly.
Interval partitioning (minimum rooms, earlier in this lesson) is the model example. Depth = the largest number of intervals that all contain one common time point. Any schedule needs at least rooms, since those intervals pairwise overlap. The heap algorithm opens a new room only when every open room is busy at the new start time ; then is covered by all the busy intervals plus the new one, so the number of rooms never exceeds . Greedy uses exactly the lower bound, so it is optimal. The full proof is in Intervals.
Technique 4: the cut property (and matroids)
For graphs, the exchange argument has a standard packaged form. Cut property: for any split of the vertices into two sides, a lightest edge crossing the split belongs to some minimum spanning tree. Kruskal and Prim are both "repeatedly add an edge the cut property says is safe". The proof (swap the light edge into any MST and delete the heavier crossing edge on the cycle it creates) is written out in full in Minimum Spanning Trees. The matroid section below shows that the cut property is a special case of a much more general theorem.
A recipe you can use under pressure
- State the rule precisely, including how ties are broken.
- Hunt for a counterexample for two minutes with 2–4 elements. Try: one long item vs several short ones, equal keys, an item that is great on one measure and terrible on another.
- If none appears, pick the technique: set/order → exchange; built in rounds → stays ahead; counting resources → structural bound; edges/independent sets → cut property or matroid.
- Write the swap (or the induction step) on one concrete pair. If you cannot say why the swap does not hurt, you probably have the wrong rule.
- Cross-check with a brute force on random small inputs. All the greedy claims on this page were checked this way.
Interval Scheduling Variants
Interval Partitioning (Minimum Rooms)
Problem: Given intervals, find the minimum number of rooms/resources needed so no two overlapping intervals share a room.
Greedy strategy: Sort by start time. Use a min-heap to track the earliest ending room. If the earliest-ending room is free, reuse it. Otherwise, allocate a new room.
TypeScript:
function minRooms(intervals: [number, number][]): number {
if (intervals.length === 0) return 0;
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
// Min-heap of end times (simulated with sorted array)
const endTimes: number[] = [sorted[0][1]];
for (let i = 1; i < sorted.length; i++) {
const [start, end] = sorted[i];
// Find the earliest ending room
endTimes.sort((a, b) => a - b);
if (start >= endTimes[0]) {
endTimes.shift(); // reuse this room
}
endTimes.push(end);
}
return endTimes.length;
}
Python:
import heapq
def min_rooms(intervals: list[tuple[int, int]]) -> int:
if not intervals:
return 0
sorted_intervals = sorted(intervals, key=lambda x: x[0])
heap = [sorted_intervals[0][1]] # end time of first interval
for start, end in sorted_intervals[1:]:
if start >= heap[0]:
heapq.heapreplace(heap, end) # reuse room
else:
heapq.heappush(heap, end) # new room
return len(heap)
TIP
The minimum number of rooms equals the maximum number of overlapping intervals at any point. This is the "depth" of the interval set. The greedy approach with a heap computes this in .
Weighted Interval Scheduling
When intervals have weights (profits), greedy no longer works — you need DP. This is a critical distinction for interviews.
where is the latest interval that does not overlap with .
Huffman Coding
Huffman coding produces an optimal prefix-free binary code for a set of characters based on their frequencies. Characters that appear more frequently get shorter codes.
graph TD
R["100"] --> L["40"]
R --> RI["60"]
L --> LL["a: 20"]
L --> LR["b: 20"]
RI --> RL["c: 25"]
RI --> RR["35"]
RR --> RRL["d: 15"]
RR --> RRR["e: 20"]
style LL fill:#4caf50,color:#fff
style LR fill:#4caf50,color:#fff
style RL fill:#4caf50,color:#fff
style RRL fill:#4caf50,color:#fff
style RRR fill:#4caf50,color:#fff
Algorithm:
- Create a leaf node for each character with its frequency
- Insert all nodes into a min-heap (priority queue)
- While the heap has more than one node:
- Extract the two nodes with minimum frequency
- Create a new internal node with these two as children, frequency = sum
- Insert the new node back into the heap
- The remaining node is the root of the Huffman tree
TypeScript:
interface HuffmanNode {
char: string | null;
freq: number;
left: HuffmanNode | null;
right: HuffmanNode | null;
}
function buildHuffmanTree(freqs: Map<string, number>): HuffmanNode {
// Simple priority queue (use a proper heap in production)
const nodes: HuffmanNode[] = [];
for (const [char, freq] of freqs) {
nodes.push({ char, freq, left: null, right: null });
}
while (nodes.length > 1) {
nodes.sort((a, b) => a.freq - b.freq);
const left = nodes.shift()!;
const right = nodes.shift()!;
const parent: HuffmanNode = {
char: null,
freq: left.freq + right.freq,
left,
right,
};
nodes.push(parent);
}
return nodes[0];
}
function generateCodes(
node: HuffmanNode | null,
prefix = "",
codes = new Map<string, string>()
): Map<string, string> {
if (!node) return codes;
if (node.char !== null) {
codes.set(node.char, prefix || "0");
return codes;
}
generateCodes(node.left, prefix + "0", codes);
generateCodes(node.right, prefix + "1", codes);
return codes;
}
Python:
import heapq
from dataclasses import dataclass, field
@dataclass(order=True)
class HuffmanNode:
freq: int
char: str | None = field(compare=False, default=None)
left: 'HuffmanNode | None' = field(compare=False, default=None)
right: 'HuffmanNode | None' = field(compare=False, default=None)
def build_huffman_tree(freqs: dict[str, int]) -> HuffmanNode:
heap = [HuffmanNode(freq=f, char=c) for c, f in freqs.items()]
heapq.heapify(heap)
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = HuffmanNode(
freq=left.freq + right.freq,
left=left,
right=right
)
heapq.heappush(heap, merged)
return heap[0]
def generate_codes(
node: HuffmanNode | None,
prefix: str = "",
codes: dict[str, str] | None = None
) -> dict[str, str]:
if codes is None:
codes = {}
if node is None:
return codes
if node.char is not None:
codes[node.char] = prefix or "0"
return codes
generate_codes(node.left, prefix + "0", codes)
generate_codes(node.right, prefix + "1", codes)
return codes
Huffman Optimality
Huffman coding produces the optimal prefix-free code. The expected code length is:
where is the probability of character and is its code length. The lower bound is the entropy:
Huffman coding satisfies .
Huffman trace table
Take the classic CLRS example: a file of 100,000 characters using six letters with frequencies (in thousands) a:45, b:13, c:12, d:16, e:9, f:5. Ties are broken by "smaller weight, then older node first". Each row merges the two lightest subtrees in the heap.
| Step | Heap before (weights) | Pop | Pop | New node | Every letter under it gets one bit longer |
|---|---|---|---|---|---|
| 1 | 5, 9, 12, 13, 16, 45 | f:5 | e:9 | 14 | f, e |
| 2 | 12, 13, 14, 16, 45 | c:12 | b:13 | 25 | c, b |
| 3 | 14, 16, 25, 45 | (fe):14 | d:16 | 30 | f, e, d |
| 4 | 25, 30, 45 | (cb):25 | (fed):30 | 55 | c, b, f, e, d |
| 5 | 45, 55 | a:45 | (cbfed):55 | 100 (root) | everything |
Final code lengths: a = 1, b = c = d = 3, e = f = 4. Total bits thousand, i.e. 2.24 bits per character. A fixed-length code needs 3 bits for six letters (300 thousand bits), so Huffman saves 25%. The entropy of this distribution is bits, so Huffman is within 0.02 bits of the theoretical floor here. A useful fact: the total cost equals the sum of the weights of all internal nodes (), because each merge adds one bit to every character beneath it. That is why "merge sticks / ropes / files, cost = sum of sizes" problems are Huffman in disguise.
For the five-letter tree drawn above (a:20, b:20, c:25, d:15, e:20), the cost is , i.e. 2.35 bits per letter. Different tie-breaking can give a differently shaped tree, but always the same total cost.
Huffman correctness: proof sketch
Model a prefix code as a binary tree: letters at leaves, a codeword is the path from the root (left = 0, right = 1). The cost of a tree is . Two lemmas, both exchange arguments (CLRS §15.3, 4th ed.):
- Greedy choice. Let be the two rarest letters. Some optimal tree has and as siblings at the maximum depth. Why: an optimal tree is full (every internal node has two children — otherwise you could shorten a code), so the deepest level has two sibling leaves . Swap the leaves and . Write for their depths before the swap; because is at maximum depth, and because is rarest. The cost changes by . Do the same for and . The cost does not go up, so the new tree is still optimal.
- Optimal substructure. Replace and by one new letter with . If is optimal for the reduced alphabet, then splitting leaf into children gives an optimal for the original, because — the extra cost is a constant that does not depend on the shape of .
Huffman's algorithm is exactly "merge the two rarest, recurse on the reduced alphabet", so induction on the alphabet size finishes the proof.
"Optimal" has fine print
Huffman is optimal among codes that assign a whole number of bits to each symbol independently. Arithmetic coding and asymmetric numeral systems (ANS, used in Zstandard) beat it on skewed distributions — e.g. a symbol with probability 0.99 costs Huffman a full bit but carries only about 0.015 bits of information. And when code lengths are capped (DEFLATE allows at most 15 bits), plain Huffman can violate the cap; the length-limited optimum is found by the package-merge algorithm (Larmore and Hirschberg, 1990), while zlib uses a heuristic adjustment.
Fractional Knapsack
Problem: Given items with weights and values, and a knapsack capacity , maximize value. You can take fractions of items.
Greedy strategy: Sort items by value-to-weight ratio. Take items in decreasing ratio order, taking fractions of the last item if needed.
WARNING
Fractional knapsack is solvable by greedy. 0/1 knapsack (must take whole items or nothing) requires DP. This distinction comes up frequently in interviews.
TypeScript:
interface Item {
weight: number;
value: number;
}
function fractionalKnapsack(items: Item[], capacity: number): number {
// Sort by value-to-weight ratio (descending)
const sorted = [...items].sort(
(a, b) => b.value / b.weight - a.value / a.weight
);
let totalValue = 0;
let remaining = capacity;
for (const item of sorted) {
if (remaining <= 0) break;
if (item.weight <= remaining) {
// Take the whole item
totalValue += item.value;
remaining -= item.weight;
} else {
// Take a fraction
const fraction = remaining / item.weight;
totalValue += item.value * fraction;
remaining = 0;
}
}
return totalValue;
}
Python:
def fractional_knapsack(items: list[tuple[int, int]], capacity: int) -> float:
"""Items are (weight, value) tuples."""
# Sort by value/weight ratio descending
sorted_items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)
total_value = 0.0
remaining = capacity
for weight, value in sorted_items:
if remaining <= 0:
break
if weight <= remaining:
total_value += value
remaining -= weight
else:
fraction = remaining / weight
total_value += value * fraction
remaining = 0
return total_value
# Example
items = [(10, 60), (20, 100), (30, 120)] # (weight, value)
print(fractional_knapsack(items, 50)) # 240.0
Minimum Spanning Trees
A minimum spanning tree (MST) of a connected, weighted, undirected graph is a subset of edges that connects all vertices with the minimum total edge weight. It has exactly edges.
graph LR
A --- |4| B
A --- |8| H
B --- |8| C
B --- |11| H
C --- |7| D
C --- |2| F
D --- |9| E
D --- |14| F
E --- |10| F
F --- |4| G
G --- |1| H
G --- |2| I
H --- |7| I
Cut Property
For any cut of the graph, the minimum weight edge crossing the cut belongs to some MST. This is the theoretical foundation for both Prim's and Kruskal's algorithms.
Kruskal's Algorithm
Strategy: Sort all edges by weight. Add edges in order, skipping any edge that would create a cycle. Uses Union-Find to detect cycles efficiently.
TypeScript:
class UnionFind {
parent: number[];
rank: number[];
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
union(x: number, y: number): boolean {
const px = this.find(x);
const py = this.find(y);
if (px === py) return false; // already connected
// union by rank
if (this.rank[px] < this.rank[py]) {
this.parent[px] = py;
} else if (this.rank[px] > this.rank[py]) {
this.parent[py] = px;
} else {
this.parent[py] = px;
this.rank[px]++;
}
return true;
}
}
function kruskal(
n: number,
edges: [number, number, number][]
): [number, number, number][] {
edges.sort((a, b) => a[2] - b[2]); // sort by weight
const uf = new UnionFind(n);
const mst: [number, number, number][] = [];
for (const [u, v, w] of edges) {
if (uf.union(u, v)) {
mst.push([u, v, w]);
if (mst.length === n - 1) break;
}
}
return mst;
}
Python:
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: int, y: int) -> bool:
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def kruskal(n: int, edges: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
edges.sort(key=lambda e: e[2])
uf = UnionFind(n)
mst = []
for u, v, w in edges:
if uf.union(u, v):
mst.append((u, v, w))
if len(mst) == n - 1:
break
return mst
Prim's Algorithm
Strategy: Start from any vertex. Repeatedly add the cheapest edge connecting a visited vertex to an unvisited vertex. Uses a min-heap for efficiency.
TypeScript:
function prim(
n: number,
adj: Map<number, [number, number][]>
): [number, number, number][] {
const visited = new Set<number>();
const mst: [number, number, number][] = [];
// Min-heap: [weight, from, to]
let heap: [number, number, number][] = [];
visited.add(0);
for (const [neighbor, weight] of adj.get(0) ?? []) {
heap.push([weight, 0, neighbor]);
}
heap.sort((a, b) => a[0] - b[0]);
while (heap.length > 0 && mst.length < n - 1) {
const [w, u, v] = heap.shift()!;
if (visited.has(v)) continue;
visited.add(v);
mst.push([u, v, w]);
for (const [neighbor, weight] of adj.get(v) ?? []) {
if (!visited.has(neighbor)) {
heap.push([weight, v, neighbor]);
heap.sort((a, b) => a[0] - b[0]);
}
}
}
return mst;
}
Python:
import heapq
def prim(n: int, adj: dict[int, list[tuple[int, int]]]) -> list[tuple[int, int, int]]:
visited = set()
mst: list[tuple[int, int, int]] = []
# (weight, from, to)
heap: list[tuple[int, int, int]] = [(w, 0, v) for v, w in adj.get(0, [])]
heapq.heapify(heap)
visited.add(0)
while heap and len(mst) < n - 1:
w, u, v = heapq.heappop(heap)
if v in visited:
continue
visited.add(v)
mst.append((u, v, w))
for neighbor, weight in adj.get(v, []):
if neighbor not in visited:
heapq.heappush(heap, (weight, v, neighbor))
return mst
Kruskal's vs Prim's
| Aspect | Kruskal's | Prim's |
|---|---|---|
| Strategy | Edge-centric (sort all edges) | Vertex-centric (grow from a vertex) |
| Data Structure | Union-Find | Min-Heap |
| Time Complexity | with binary heap | |
| Best for | Sparse graphs () | Dense graphs () |
| Implementation | Simpler | Slightly more complex |
Refinement: dense graphs
With a binary heap, Prim costs , which on a dense graph () is — no better than Kruskal. Prim's real advantage on dense graphs comes from the array version (scan an array of "best edge into the tree" values each step), which is and needs no heap at all. Both versions, plus Borůvka, are implemented and compared in Minimum Spanning Trees.
Matroids: why greedy works when it works
Kruskal's rule — "take the cheapest edge that does not create a cycle" — and the rule "take the most valuable items" look unrelated. They are the same algorithm on two different matroids, and that is not a coincidence.
What a matroid is
A matroid is a finite ground set plus a family of subsets of called independent sets, satisfying three rules:
- Non-empty: the empty set is independent.
- Hereditary: every subset of an independent set is independent. (If you can keep a set of edges without a cycle, you can keep any part of it.)
- Exchange: if and are independent and , then some element can be added to with still independent. (A smaller independent set can always "borrow" from a bigger one.)
A maximal independent set is called a basis. Rule 3 implies all bases have the same size (the rank).
Examples:
| Matroid | Ground set | Independent = | Greedy on it is… |
|---|---|---|---|
| Uniform | items | any set of at most items | "take the most valuable" |
| Graphic | edges of a graph | edge sets with no cycle (forests) | Kruskal's algorithm (max or min spanning forest) |
| Linear | vectors | linearly independent sets | max-weight basis of a vector space |
| Scheduling | unit-time jobs with deadlines | sets of jobs that can all finish on time | max-profit job sequencing (CLRS 3rd ed. §16.5) |
| Partition | items in colour classes | at most items of each colour | "best of each colour" |
Why is the graphic matroid's exchange rule true? A forest with edges on vertices has connected components. If , then 's forest has fewer components than 's, so some edge of joins two different components of — and adding it to creates no cycle.
The theorem (Rado 1957, Edmonds 1971)
Give each element a weight . The matroid greedy algorithm sorts elements by decreasing weight and adds each element if the set stays independent.
Theorem. For a matroid, the greedy algorithm returns a maximum-weight independent set (for every choice of weights). Conversely, if is hereditary and greedy is optimal for every weight function, then satisfies the exchange rule — i.e. it is a matroid.
Proof sketch (the "if" direction). Let greedy pick in order (so ), and let be any independent set sorted the same way. Claim: for every (and ). Suppose not, and let be the first index with . Apply the exchange rule to and : some with can be added to . Its weight is , so greedy would have considered before , and at that moment its chosen set was a subset of , so by the hereditary rule adding was allowed — greedy would have taken it. Contradiction. Summing gives .
This is the stays-ahead technique in its most general form. Minimum spanning tree is the same theorem with weights for a large constant (every spanning tree has edges, so maximising is minimising ), and the cut property is the graphic matroid's version of the exchange step.
Non-examples, and what they teach
- 0/1 knapsack is not a matroid. "Total weight at most the capacity" is hereditary, but the exchange rule breaks. Capacity 50, items of weight 10, 20 and 50: and are both feasible and , yet adding 10 or 20 to overflows the bag. Maximal feasible sets of different sizes are exactly what a matroid forbids, and that is why greedy-by-ratio fails there (numbers in the next section).
- Matchings in a general graph are hereditary but break the exchange rule (on a path , the matching is maximal while is bigger, and neither nor can be added to ). Maximum matching needs augmenting paths — see Bipartite Matching. Bipartite matchings are the intersection of two matroids, where greedy gives only a 1/2-approximation.
- Shortest Hamiltonian path / travelling salesman: not a matroid, and greedy "nearest neighbour" can be arbitrarily bad.
You do not need matroid theory to pass an interview. But when you meet a new "pick the best subset" problem, asking "does a small independent set always borrow from a bigger one?" is a fast way to guess whether greedy has a chance.
When Greedy Fails
Greedy algorithms fail when the greedy choice property does not hold. Recognizing these cases is critical for interviews.
Classic Failures
| Problem | Why Greedy Fails | Correct Approach |
|---|---|---|
| 0/1 Knapsack | Taking highest ratio item may block a better combination | DP |
| Coin Change (arbitrary denominations) | Largest coin first can miss valid combinations | DP |
| Longest Path in general graph | Greedy shortest path logic does not reverse | DP or backtracking |
| Traveling Salesman | Nearest neighbor heuristic gives suboptimal tours | DP with bitmask |
Correction: longest path
"DP or backtracking" for the longest path needs a qualifier. On a DAG, longest path is easy DP in topological order (; see Topological Sort). In a general graph, the longest simple path is NP-hard (it contains Hamiltonian path as a special case), so no known DP is polynomial; exact methods are exponential (bitmask DP in or backtracking). Likewise, the bitmask DP for TSP (Held–Karp) is exact but takes time.
Coin Change Example
With denominations and target :
- Greedy: coins
- Optimal: coins
Greedy fails because taking the largest coin first blocks a better combination.
Interview Signal
When asked "can we use greedy here?", the strongest answer is to either:
- Prove it works with an exchange argument, or
- Give a counterexample showing it fails
Don't just say "I think greedy works." Justify or refute it.
Counterexamples, checked by script
Every number in this subsection was produced by a script that runs the greedy rule and an exhaustive or DP optimum side by side.
Coin systems. "Largest coin first" against a DP that finds the true minimum:
| Coins | Amount | Greedy picks | Greedy count | Optimal | Optimal count |
|---|---|---|---|---|---|
| 6 | 4 + 1 + 1 | 3 | 3 + 3 | 2 | |
| 14 | 10 + 1 + 1 + 1 + 1 | 5 | 7 + 7 | 2 | |
| (US coins without the nickel) | 30 | 25 + 1 + 1 + 1 + 1 + 1 | 6 | 10 + 10 + 10 | 3 |
| 40 | 25 + 10 + 5 | 3 | 20 + 20 | 2 | |
| (US) | any | — | — | greedy always optimal | — |
A coin system where greedy is always optimal is called canonical. US coins , euro coins and pound coins are all canonical; our script confirmed it by checking every amount below the sum of the two largest coins. That bound is a theorem: Kozen and Zaks (1994) proved that if a system with largest coins is not canonical, its smallest counterexample is below , so a finite check settles the question. Pearson (2005) gave an test. For arbitrary coins, use the DP — see Knapsack.
0/1 knapsack versus fractional knapsack. Same three items as the fractional example above: (weight 10, value 60), (20, 100), (30, 120); capacity 50. Ratios are 6, 5, 4.
| Version | Rule | Takes | Value |
|---|---|---|---|
| Fractional | best ratio first, split the last item | all of 10 and 20, two thirds of 30 | 240 (optimal) |
| 0/1, greedy by ratio | best ratio first, whole items only | 10 and 20 (30 no longer fits) | 160 |
| 0/1, optimal (checked over all 8 subsets) | DP or brute force | 20 and 30 | 220 |
Greedy-by-ratio loses 60 in the 0/1 version because the high-ratio small item wastes 20 units of capacity that only the 30-item could have used well. In the fractional version that waste is impossible: the leftover space is filled with a fraction of the next-best item. Exchange argument for fractional: if an optimal solution takes less of a higher-ratio item and some of a lower-ratio item , move weight from to ; value changes by . In 0/1 you cannot move — only whole items — so the argument collapses.
Dijkstra with a negative edge. Dijkstra is a greedy algorithm: it permanently settles the closest unsettled vertex. With edges (2), (5), (), it settles at distance 2, but the true distance is . The stays-ahead proof needs "a path can only get longer as it grows", which negative edges break. Use Bellman–Ford instead (Shortest Paths).
Weighted interval scheduling. Intervals worth 10, worth 6, worth 6. Earliest finish picks and for 12 — that happens to win. Change the long one to worth 13 and earliest-finish still says 12, while the optimum is 13. "Heaviest first" fails the other way (make the two short ones worth 7 each). No single sort order works once weights appear; the DP from the formula above is the answer.
Common Greedy Problems for Interviews
| Problem | Greedy Criterion | Complexity |
|---|---|---|
| Activity Selection | Earliest finish time | |
| Job Sequencing with Deadlines | Highest profit first | or |
| Huffman Coding | Lowest frequency merge | |
| Fractional Knapsack | Highest value/weight ratio | |
| Minimum Platforms | Sort arrivals + departures | |
| Gas Station Circuit | Net fuel surplus | |
| Jump Game | Maximum reachable index | |
| Task Scheduler | Most frequent task first | |
| Candy | Two passes, each fixing one neighbour rule | |
| Two-City Scheduling | Sort by cost difference |
Classic greedy interview problems, worked
Six problems that show up again and again. For each: the rule, a worked example (numbers checked by script), and why the rule is right. The first three tie back to the proof techniques above.
Jump game I: can you reach the end?
You stand on index 0 of an array; nums[i] is the longest jump allowed from index . Can you reach the last index?
Rule: scan left to right keeping farthest, the largest index reachable so far. If you ever stand at farthest, you are stuck. Otherwise update farthest = max(farthest, i + nums[i]).
On [2, 3, 1, 1, 4] farthest goes 2, 4, 4, 4, 8 → reachable. On [3, 2, 1, 0, 4] it goes 3, 3, 3, 3 and index 4 is beyond it → stuck at the 0.
Why: the set of reachable indices is always a prefix (if you can reach , you can reach every on the way, because jumps may be shorter than the maximum). So one number describes it exactly. time, space.
Jump game II: fewest jumps
Same array, the end is guaranteed reachable; minimise the number of jumps.
Rule (BFS by levels, done greedily): the indices reachable with exactly jumps form a contiguous window. Scan the current window, recording the farthest index any of them can reach; when you finish the window, take one jump and the next window ends at that farthest index.
Trace on [2, 1, 2, 3, 1, 1, 1, 1] (8 indices; we scan because standing on the last index needs no jump):
nums[i] | $i + $ nums[i] | farthest after | = window end? | Jumps | Window end after | |
|---|---|---|---|---|---|---|
| 0 | 2 | 2 | 2 | yes | 1 | 2 |
| 1 | 1 | 2 | 2 | no | 1 | 2 |
| 2 | 2 | 4 | 4 | yes | 2 | 4 |
| 3 | 3 | 6 | 6 | no | 2 | 4 |
| 4 | 1 | 5 | 6 | yes | 3 | 6 |
| 5 | 1 | 6 | 6 | no | 3 | 6 |
| 6 | 1 | 7 | 7 | yes | 4 | 7 |
Answer 4, e.g. . The windows are , , , , : exactly the BFS levels of the "can jump to" graph, found without a queue.
flowchart LR
L0["level 0: index 0"] -->|"jump 1"| L1["level 1: indices 1-2"]
L1 -->|"jump 2"| L2["level 2: indices 3-4"]
L2 -->|"jump 3"| L3["level 3: indices 5-6"]
L3 -->|"jump 4"| L4["level 4: index 7"]
Why (greedy stays ahead): let be the farthest index reachable in jumps by any strategy. Every index up to is reachable in at most jumps (prefix property again), and — exactly what the scan computes. So after jumps the greedy window reaches , as far as anything can, and the first with is the answer. Checked against a BFS on 3,000 random arrays. time, space. Full code in four languages is in Implementation.
Gas station: where to start a circular route
Stations on a loop; station gives gas[i] fuel and driving to costs cost[i]. Find the unique start that lets you complete the loop, or .
Rule: if total gas < total cost, return . Otherwise drive from station 0 keeping a running tank; whenever tank drops below 0 after leaving station , the start must be after : set start = i + 1, tank = 0.
Example: gas = [1,2,3,4,5], cost = [3,4,5,1,2]. Net gains ; total . Tank: (reset, start 1), (reset, start 2), (reset, start 3), 3, 6. Answer 3. With gas = [2,3,4], cost = [3,4,3] the total is : answer .
Why: (a) If you start at and first run dry going from to , then no station between and works as a start either: you arrived at each of them with a tank , so starting there with 0 can only be worse. That justifies skipping the whole block in one step. (b) Let be the running sum of net gains through station . A reset happens exactly when hits a new low below every earlier value, so the final start sits just after the first place where is lowest (or at 0 if never goes negative). Starting there, the fuel after station is before wrapping around, and after wrapping, because the total is . Checked against trying every start on 3,000 random inputs. .
Task scheduler: idle slots around the most frequent task
Tasks are letters; equal letters must be at least slots apart (other tasks or idle in between). Minimum total slots?
Formula: let be the highest frequency and the number of letters with that frequency. Answer .
Picture "frames" of length , each starting with the most frequent letter, plus a final partial frame holding the letters tied for most frequent. Other letters fill the gaps. If they overflow the frames, no idle slot is needed at all and the answer is just the number of tasks.
| Tasks | Answer | ||||
|---|---|---|---|---|---|
| AAABBB | 2 | 3 | 2 | 8 | 8 (A B _ A B _ A B) |
| AAABBB | 0 | 3 | 2 | 4 | 6 (no cool-down) |
| AAAAAABCDEFG | 2 | 6 | 1 | 16 | 16 |
| ACABDB | 1 | 2 | 2 | 4 | 6 |
Why it is a lower bound: the copies of the most frequent letter need gaps of after the first copies, and every letter tied at must also appear in the last stretch. Why greedy meets it: "always run the available task with the most remaining copies" (a max-heap simulation) never idles unless every remaining task is cooling down, which only happens inside the frames. to count.
Candy: two passes
Children stand in a row with ratings. Each gets at least one candy, and a child with a higher rating than a neighbour gets more than that neighbour. Minimise the total.
Rule: start everyone at 1. Left-to-right: if r[i] > r[i-1], set c[i] = c[i-1] + 1. Right-to-left: if r[i] > r[i+1], set c[i] = max(c[i], c[i+1] + 1).
| Ratings | After left pass | After right pass | Total |
|---|---|---|---|
| 1, 0, 2 | 1, 1, 2 | 2, 1, 2 | 5 |
| 1, 2, 2 | 1, 2, 1 | 1, 2, 1 | 4 |
| 1, 2, 87, 87, 87, 2, 1 | 1, 2, 3, 1, 1, 1, 1 | 1, 2, 3, 1, 3, 2, 1 | 13 |
Why: the left pass gives the smallest values satisfying every left-neighbour rule; the right pass gives the smallest satisfying every right-neighbour rule; taking the max of the two satisfies both, and any valid assignment must be at least each of them pointwise (by induction along each increasing run), so it must be at least their max. Equal ratings impose no constraint, which is why the middle 87 gets 1. .
Two-city scheduling: sort by the difference
people; person costs to fly to city A and to city B. Exactly go to each city. Minimise total cost.
Rule: sort by (how much cheaper A is, most negative first). Send the first to A, the rest to B.
Example [[10,20],[30,200],[400,50],[30,20]]: differences . Sorted: . A gets the first two (), B the rest (): 110.
Why (exchange): suppose an optimal assignment sends to B and to A with . Swapping them changes the cost by — strictly better, contradiction. So in an optimal answer everyone in A has a smaller difference than everyone in B, which is the sorted split. Checked against all splits on 500 random inputs. .
Complexity Summary
graph LR
subgraph "Greedy vs DP Decision"
A["Can you prove<br/>greedy choice property?"] -->|Yes| B["Greedy<br/>O(n log n) typical"]
A -->|No| C["Use DP<br/>O(n * states)"]
A -->|Unsure| D["Try counterexample<br/>If fails → DP"]
end
Complexity table
| Algorithm | Time | Extra space | Dominant cost |
|---|---|---|---|
| Activity selection | ; if already sorted by finish | beyond the output (or for a sorted copy) | the sort |
| Interval partitioning (rooms) | heap | sort + heap operations | |
| Minimise max lateness (EDF) | the sort | ||
| Fractional knapsack | ; with weighted-median selection | the sort | |
| Huffman coding | ; if frequencies arrive sorted (two-queue method) | heap pops | |
| Kruskal | union-find | sorting edges | |
| Prim (binary heap / array) | / | heap operations | |
| Jump game I and II | one scan | ||
| Gas station | one scan | ||
| Task scheduler | counts | counting | |
| Candy | two scans | ||
| Two-city scheduling | the sort |
The pattern: a greedy algorithm usually costs one sort plus one linear scan, or heap operations. Best, average and worst case are the same for all of these (no early exits that matter), except that inputs which arrive pre-sorted skip the factor.
Deeper: Huffman in linear time after sorting
If the frequencies are already sorted, keep two FIFO queues: the leaves in increasing order, and the merged nodes in the order they are created. Merged weights are created in non-decreasing order, so the smallest remaining item is always at the front of one of the two queues. Each step compares two fronts: total, no heap (van Leeuwen, 1976).
The ladder: brute force → better → optimal
Problem: maximum number of compatible intervals (activity selection), intervals.
Rung 1: try every subset
Enumerate all subsets, keep those with no overlap, return the largest. . At that is a billion subsets — fine as a test oracle for , which is exactly how this lesson's claims were checked.
Rung 2: dynamic programming
Sort by finish time. Let be the answer using only the first intervals. Either interval is out (), or it is in and we add , where is the last interval finishing by (found by binary search). — and this is the version that survives when intervals get weights (the weighted interval scheduling formula above).
Rung 3: greedy
The exchange argument says "is in?" never needs to be asked: the earliest finisher is always safe. One sort, one scan, , extra space, and if the input is already sorted by finish time.
| Rung | Method | Time | Space | Why it is better than the rung above |
|---|---|---|---|---|
| 1 | All subsets | Obviously correct; the oracle for testing | ||
| 2 | DP + binary search | Polynomial; handles weights | ||
| 3 | Greedy by finish | , or presorted | No table, two lines of logic, streams over sorted input |
The same ladder shape fits most greedy problems: exponential search → DP over "take it or not" → the observation that one branch is always safe. When you cannot prove that observation, stop at rung 2.
Implementation
One program per language, covering the three algorithms this lesson leans on hardest: activity selection, Huffman code lengths (the part DEFLATE actually stores — see Real-world uses) and jump game II. Each block runs its own tests on the examples from this lesson. Huffman ties are broken by (weight, node id) in every language so all four produce identical lengths.
import heapq
from typing import List, Tuple
def select_activities(intervals: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
"""Largest set of pairwise compatible half-open intervals [start, finish)."""
chosen: List[Tuple[int, int]] = []
last_finish = float("-inf")
for start, finish in sorted(intervals, key=lambda iv: iv[1]): # earliest finish first
if start >= last_finish: # compatible with everything chosen
chosen.append((start, finish))
last_finish = finish
return chosen
def huffman_code_lengths(freqs: List[int]) -> List[int]:
"""Length of each symbol's codeword in an optimal prefix code. Ties: (weight, node id)."""
n = len(freqs)
if n == 1:
return [1] # one symbol still needs a 1-bit code
parent = [-1] * (2 * n - 1) # nodes 0..n-1 are leaves, n..2n-2 internal
heap = [(f, i) for i, f in enumerate(freqs)]
heapq.heapify(heap)
next_id = n
while len(heap) > 1:
w1, a = heapq.heappop(heap) # the two lightest subtrees...
w2, b = heapq.heappop(heap)
parent[a] = parent[b] = next_id # ...become siblings under a new node
heapq.heappush(heap, (w1 + w2, next_id))
next_id += 1
depth = [0] * (2 * n - 1) # root is node 2n-2 at depth 0
for v in range(2 * n - 3, -1, -1): # a parent always has a larger id than its children
depth[v] = depth[parent[v]] + 1
return depth[:n]
def min_jumps(nums: List[int]) -> int:
"""Fewest jumps from index 0 to the last index (-1 if impossible)."""
jumps, window_end, farthest = 0, 0, 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i]) # best reach from the current window
if i == window_end: # current window exhausted: must jump
if farthest <= i:
return -1 # stuck: nothing reaches past i
jumps += 1
window_end = farthest
return jumps
if __name__ == "__main__":
acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
assert select_activities(acts) == [(1, 4), (5, 7), (8, 11)]
assert select_activities([]) == []
clrs = [45, 13, 12, 16, 9, 5] # a b c d e f
lengths = huffman_code_lengths(clrs)
assert lengths == [1, 3, 3, 3, 4, 4]
assert sum(f * l for f, l in zip(clrs, lengths)) == 224
assert sum(2.0 ** -l for l in lengths) == 1.0 # Kraft: a full binary tree
page = [20, 20, 25, 15, 20]
assert sum(f * l for f, l in zip(page, huffman_code_lengths(page))) == 235
assert huffman_code_lengths([7]) == [1]
assert min_jumps([2, 3, 1, 1, 4]) == 2
assert min_jumps([2, 1, 2, 3, 1, 1, 1, 1]) == 4
assert min_jumps([0]) == 0
assert min_jumps([3, 2, 1, 0, 4]) == -1
print("activity selection, huffman lengths, jump game II: all tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class Main {
/** Largest set of pairwise compatible half-open intervals [start, finish). */
static List<int[]> selectActivities(int[][] intervals) {
int[][] sorted = intervals.clone();
Arrays.sort(sorted, (x, y) -> Integer.compare(x[1], y[1])); // earliest finish first
List<int[]> chosen = new ArrayList<>();
long lastFinish = Long.MIN_VALUE;
for (int[] iv : sorted) {
if (iv[0] >= lastFinish) {
chosen.add(iv);
lastFinish = iv[1];
}
}
return chosen;
}
/** Codeword length per symbol in an optimal prefix code. Ties: (weight, node id). */
static int[] huffmanCodeLengths(long[] freqs) {
int n = freqs.length;
if (n == 1) return new int[] {1};
int[] parent = new int[2 * n - 1];
long[] weight = new long[2 * n - 1];
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) ->
weight[a] != weight[b] ? Long.compare(weight[a], weight[b]) : Integer.compare(a, b));
for (int i = 0; i < n; i++) { weight[i] = freqs[i]; heap.add(i); }
int nextId = n;
while (heap.size() > 1) {
int a = heap.poll(), b = heap.poll(); // the two lightest subtrees
weight[nextId] = weight[a] + weight[b];
parent[a] = nextId;
parent[b] = nextId;
heap.add(nextId++);
}
int[] depth = new int[2 * n - 1]; // root = 2n-2, depth 0
for (int v = 2 * n - 3; v >= 0; v--) depth[v] = depth[parent[v]] + 1;
return Arrays.copyOf(depth, n);
}
/** Fewest jumps from index 0 to the last index, or -1 if impossible. */
static int minJumps(int[] nums) {
int jumps = 0, windowEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == windowEnd) {
if (farthest <= i) return -1;
jumps++;
windowEnd = farthest;
}
}
return jumps;
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
int[][] acts = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}};
List<int[]> got = selectActivities(acts);
check(got.size() == 3 && got.get(0)[0] == 1 && got.get(1)[0] == 5 && got.get(2)[0] == 8, "activities");
check(selectActivities(new int[0][]).isEmpty(), "empty");
long[] clrs = {45, 13, 12, 16, 9, 5};
int[] len = huffmanCodeLengths(clrs);
check(Arrays.equals(len, new int[] {1, 3, 3, 3, 4, 4}), "huffman lengths");
long cost = 0;
for (int i = 0; i < clrs.length; i++) cost += clrs[i] * len[i];
check(cost == 224, "huffman cost");
long[] page = {20, 20, 25, 15, 20};
int[] len2 = huffmanCodeLengths(page);
long cost2 = 0;
for (int i = 0; i < page.length; i++) cost2 += page[i] * len2[i];
check(cost2 == 235, "huffman cost 2");
check(huffmanCodeLengths(new long[] {7})[0] == 1, "single symbol");
check(minJumps(new int[] {2, 3, 1, 1, 4}) == 2, "jumps 1");
check(minJumps(new int[] {2, 1, 2, 3, 1, 1, 1, 1}) == 4, "jumps 2");
check(minJumps(new int[] {0}) == 0, "jumps 3");
check(minJumps(new int[] {3, 2, 1, 0, 4}) == -1, "jumps 4");
System.out.println("activity selection, huffman lengths, jump game II: all tests passed");
}
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
// Largest set of pairwise compatible half-open intervals [start, finish).
vector<pair<int, int>> selectActivities(vector<pair<int, int>> iv) {
sort(iv.begin(), iv.end(), [](const auto& a, const auto& b) { return a.second < b.second; });
vector<pair<int, int>> chosen;
long long lastFinish = LLONG_MIN;
for (const auto& [s, f] : iv) {
if (s >= lastFinish) {
chosen.push_back({s, f});
lastFinish = f;
}
}
return chosen;
}
// Codeword length per symbol in an optimal prefix code. Ties: (weight, node id).
vector<int> huffmanCodeLengths(const vector<long long>& freqs) {
int n = (int)freqs.size();
if (n == 1) return {1};
vector<int> parent(2 * n - 1, -1);
using Item = pair<long long, int>; // (weight, node id)
priority_queue<Item, vector<Item>, greater<Item>> heap; // min-heap
for (int i = 0; i < n; i++) heap.push({freqs[i], i});
int nextId = n;
while (heap.size() > 1) {
auto [w1, a] = heap.top(); heap.pop();
auto [w2, b] = heap.top(); heap.pop();
parent[a] = parent[b] = nextId;
heap.push({w1 + w2, nextId++});
}
vector<int> depth(2 * n - 1, 0); // root = 2n-2
for (int v = 2 * n - 3; v >= 0; v--) depth[v] = depth[parent[v]] + 1;
return vector<int>(depth.begin(), depth.begin() + n);
}
// Fewest jumps from index 0 to the last index, or -1 if impossible.
int minJumps(const vector<int>& nums) {
int jumps = 0, windowEnd = 0, farthest = 0;
for (int i = 0; i + 1 < (int)nums.size(); i++) {
farthest = max(farthest, i + nums[i]);
if (i == windowEnd) {
if (farthest <= i) return -1;
jumps++;
windowEnd = farthest;
}
}
return jumps;
}
int main() {
vector<pair<int, int>> acts = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}};
assert((selectActivities(acts) == vector<pair<int, int>>{{1, 4}, {5, 7}, {8, 11}}));
assert(selectActivities({}).empty());
vector<long long> clrs = {45, 13, 12, 16, 9, 5};
vector<int> len = huffmanCodeLengths(clrs);
assert((len == vector<int>{1, 3, 3, 3, 4, 4}));
long long cost = 0;
for (size_t i = 0; i < clrs.size(); i++) cost += clrs[i] * len[i];
assert(cost == 224);
vector<long long> page = {20, 20, 25, 15, 20};
vector<int> len2 = huffmanCodeLengths(page);
long long cost2 = 0;
for (size_t i = 0; i < page.size(); i++) cost2 += page[i] * len2[i];
assert(cost2 == 235);
assert(huffmanCodeLengths({7}) == vector<int>{1});
assert(minJumps({2, 3, 1, 1, 4}) == 2);
assert(minJumps({2, 1, 2, 3, 1, 1, 1, 1}) == 4);
assert(minJumps({0}) == 0);
assert(minJumps({3, 2, 1, 0, 4}) == -1);
cout << "activity selection, huffman lengths, jump game II: all tests passed\n";
}
type Interval = [number, number];
// Largest set of pairwise compatible half-open intervals [start, finish).
function selectActivities(intervals: Interval[]): Interval[] {
const sorted = [...intervals].sort((a, b) => a[1] - b[1]); // earliest finish first
const chosen: Interval[] = [];
let lastFinish = -Infinity;
for (const [s, f] of sorted) {
if (s >= lastFinish) {
chosen.push([s, f]);
lastFinish = f;
}
}
return chosen;
}
// Minimal binary heap of node ids, ordered by (weight, id).
class MinHeap {
private a: number[] = [];
private w: number[];
constructor(w: number[]) {
this.w = w;
}
private less(i: number, j: number): boolean {
const x = this.a[i], y = this.a[j];
return this.w[x] !== this.w[y] ? this.w[x] < this.w[y] : x < y;
}
get size(): number {
return this.a.length;
}
push(v: number): void {
this.a.push(v);
let i = this.a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[this.a[i], this.a[p]] = [this.a[p], this.a[i]];
i = p;
}
}
pop(): number {
const top = this.a[0];
const last = this.a.pop()!;
if (this.a.length > 0) {
this.a[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < this.a.length && this.less(l, m)) m = l;
if (r < this.a.length && this.less(r, m)) m = r;
if (m === i) break;
[this.a[i], this.a[m]] = [this.a[m], this.a[i]];
i = m;
}
}
return top;
}
}
// Codeword length per symbol in an optimal prefix code. Ties: (weight, node id).
function huffmanCodeLengths(freqs: number[]): number[] {
const n = freqs.length;
if (n === 1) return [1];
const weight = new Array<number>(2 * n - 1).fill(0);
const parent = new Array<number>(2 * n - 1).fill(-1);
const heap = new MinHeap(weight);
for (let i = 0; i < n; i++) {
weight[i] = freqs[i];
heap.push(i);
}
let nextId = n;
while (heap.size > 1) {
const a = heap.pop(), b = heap.pop();
weight[nextId] = weight[a] + weight[b];
parent[a] = parent[b] = nextId;
heap.push(nextId++);
}
const depth = new Array<number>(2 * n - 1).fill(0); // root = 2n-2
for (let v = 2 * n - 3; v >= 0; v--) depth[v] = depth[parent[v]] + 1;
return depth.slice(0, n);
}
// Fewest jumps from index 0 to the last index, or -1 if impossible.
function minJumps(nums: number[]): number {
let jumps = 0, windowEnd = 0, farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i === windowEnd) {
if (farthest <= i) return -1;
jumps++;
windowEnd = farthest;
}
}
return jumps;
}
function assert(ok: boolean, what: string): void {
if (!ok) throw new Error("failed: " + what);
}
const acts: Interval[] = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11]];
assert(JSON.stringify(selectActivities(acts)) === "[[1,4],[5,7],[8,11]]", "activities");
assert(selectActivities([]).length === 0, "empty");
const clrs = [45, 13, 12, 16, 9, 5];
const len = huffmanCodeLengths(clrs);
assert(len.join(",") === "1,3,3,3,4,4", "huffman lengths");
assert(clrs.reduce((s, f, i) => s + f * len[i], 0) === 224, "huffman cost");
const page = [20, 20, 25, 15, 20];
const len2 = huffmanCodeLengths(page);
assert(page.reduce((s, f, i) => s + f * len2[i], 0) === 235, "huffman cost 2");
assert(huffmanCodeLengths([7])[0] === 1, "single symbol");
assert(minJumps([2, 3, 1, 1, 4]) === 2, "jumps 1");
assert(minJumps([2, 1, 2, 3, 1, 1, 1, 1]) === 4, "jumps 2");
assert(minJumps([0]) === 0, "jumps 3");
assert(minJumps([3, 2, 1, 0, 4]) === -1, "jumps 4");
console.log("activity selection, huffman lengths, jump game II: all tests passed");
Notes on the choices. Huffman stores a parent array instead of a tree of objects: leaves are nodes and merged nodes get increasing ids, so a parent always has a larger id than its children and one backwards loop computes all depths. A single-symbol alphabet still gets a 1-bit code (a 0-bit code cannot be decoded from a stream). Activity selection uses half-open intervals, so start >= lastFinish is the compatibility test; with closed intervals you would need >. Jump game II returns when the end is unreachable instead of looping forever.
Real-world uses
- DEFLATE (gzip, zlib, PNG, ZIP). RFC 1951 specifies Huffman coding for literals/lengths and distances after LZ77. A DEFLATE stream transmits only the code lengths; both sides rebuild the same canonical Huffman code from them (shorter codes first, ties by symbol order), which is why the code above returns lengths. Lengths are capped at 15 bits. JPEG's baseline entropy coder and HTTP/2's HPACK (a fixed Huffman table, RFC 7541) use Huffman codes too.
- Real-time schedulers. Earliest deadline first is optimal on one processor for preemptive scheduling (Liu and Layland, 1973). Linux's
SCHED_DEADLINEclass implements EDF with a constant-bandwidth server (kernel docs). See also CPU Scheduling, where shortest-job-first minimises average waiting time by the same exchange argument as this lesson. - Shortest paths. Dijkstra's algorithm is greedy: settle the closest unsettled vertex, never revisit it. Link-state routing protocols (OSPF, IS-IS) run it on every router (Shortest Paths).
- Network design and clustering. Kruskal and Prim build cheapest networks; single-linkage clustering is Kruskal stopped early (Minimum Spanning Trees).
- Caching. Bélády's offline-optimal page replacement ("evict the item used farthest in the future", 1966) is a greedy algorithm with an exchange-argument proof (CLRS 4th ed. §15.4). LRU is the online approximation.
- Approximation algorithms. When the exact problem is NP-hard, greedy is often the best practical tool with a proven bound: greedy set cover is within a factor of optimal (Johnson 1974, Chvátal 1979), and Graham's "longest processing time first" for load balancing on machines is within (1969). See Load Balancing Algorithms.
- Change-making. Vending machines and cash registers use largest-coin-first precisely because national coin systems are designed to be canonical.
Pitfalls & edge cases
- Sorting by the wrong key. Start time, duration and conflict count all fail for activity selection (counterexamples above). Write the key down and test it on three intervals.
- Closed vs half-open intervals. and overlap at 4 if closed. Decide, then use
>=or>consistently. LeetCode 435 treats touching intervals as non-overlapping; LeetCode 452 (balloons) treats touching as overlapping. - Tie-breaking that matters. EDF does not care how equal deadlines are ordered; some problems do (e.g. sort by end, then by start descending, in nested-interval problems). If ties can matter, say how you break them and test them.
- Comparator overflow.
(a, b) -> a[1] - b[1]overflows in Java/C++ for values near . UseInteger.compare. - Floating-point ratios. Sorting by
v / wwith doubles can mis-order near-equal ratios; comparev1 * w2withv2 * w1in 64-bit integers instead. - Empty input and single elements. Activity selection on
[]must return[](the original TypeScript and Python snippets above readsorted[0]unconditionally and would throw); Huffman on one symbol needs a 1-bit code; jump game on[0]needs 0 jumps. - Assuming the greedy is right because the examples pass. Interview examples are chosen to be friendly. Run a brute force on random small inputs.
- Using greedy where weights appear. "Maximum number" of intervals is greedy; "maximum total weight" is DP. "Fewest coins" with US coins is greedy; with arbitrary coins it is DP.
- Huffman with zero frequencies. Leave symbols with frequency 0 out of the tree (DEFLATE gives them length 0).
- Gas station without the total check. The reset loop alone returns a start even when the total is negative.
Variations
- Interval cover: cover a segment with the fewest given intervals — repeatedly take, among intervals starting at or before the covered point, the one reaching farthest (the jump-game-II idea on intervals).
- Minimum arrows / hitting set for intervals: sort by finish, shoot at the finish of the first un-hit interval. Same proof as activity selection — the two answers are equal.
- Scheduling with deadlines and profits (unit jobs): sort by profit, place each job in the latest free slot before its deadline (a union-find makes "latest free slot" near-). Optimal because it is a matroid.
- Course Schedule III: take courses by deadline; keep a max-heap of durations; if over the deadline, drop the longest so far. Greedy with regret.
- Greedy with a heap of "best so far": IPO, minimum refuelling stops, and many "choose items under a running constraint" problems keep a heap of candidates and pull the best when needed.
- Exchange-argument sorting with a custom comparator: "largest number from digits" (compare vs ), Johnson's rule for two-machine flow shop.
- -way Huffman: merge the smallest each time, after padding with zero-weight dummies so that .
- Greedy as a heuristic: nearest-neighbour TSP, greedy graph colouring — fast, no optimality guarantee; see Heuristics & Metaheuristics.
Practice Strategy
- Start with activity selection — the canonical greedy problem
- Implement Kruskal's and Prim's — MST is a top interview topic
- Solve Huffman coding — tests heap + greedy together
- Practice recognizing when greedy fails — coin change and 0/1 knapsack are the key counterexamples
- Always try to prove correctness — exchange arguments become natural with practice
Practice ladder
Fifteen problems, easy to hard. Each is described in my own words; follow the link for the full statement. Full solutions (tested) are given for the five that teach the most.
1. Assign Cookies (LeetCode 455) — Children have greed levels, cookies have sizes; a child is happy with a cookie at least as big as their greed. Maximise happy children.
Hint
Sort both. Walk the cookies from smallest; give each to the least greedy unhappy child it satisfies. Exchange argument: giving a bigger cookie than necessary never helps.
2. Jump Game (LeetCode 55) — Can you reach the last index? (Worked above.)
Hint
Track farthest; fail if i > farthest.
3. Movie Festival (CSES 1629) — Watch as many complete, non-overlapping movies as possible. Pure activity selection.
Solution
Sort by end time; take a movie if it starts no earlier than the last chosen one ends. .
def movie_festival(movies):
count, last = 0, 0
for a, b in sorted(movies, key=lambda m: m[1]):
if a >= last:
count += 1
last = b
return count
assert movie_festival([(3, 5), (4, 9), (5, 8)]) == 2
4. Non-overlapping Intervals (LeetCode 435) — Remove the fewest intervals so the rest do not overlap (touching is fine).
Solution
Minimum removed = − maximum kept, and maximum kept is activity selection.
def erase_overlap_intervals(intervals):
kept, last = 0, float("-inf")
for s, e in sorted(intervals, key=lambda iv: iv[1]):
if s >= last:
kept += 1
last = e
return len(intervals) - kept
assert erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]]) == 1
assert erase_overlap_intervals([[1, 2], [1, 2], [1, 2]]) == 2
5. Minimum Number of Arrows to Burst Balloons (LeetCode 452) — Balloons are closed intervals on a line; a vertical arrow at bursts every balloon containing . Fewest arrows.
Hint
Sort by end; shoot at the end of the first balloon not yet burst. Touching balloons share an arrow here (closed intervals), so the test is start > arrow.
6. Jump Game II (LeetCode 45) — Fewest jumps. Code in Implementation.
Hint
Windows = BFS levels. Jump when i reaches the end of the current window.
7. Gas Station (LeetCode 134) — Find the start of a circular route.
Solution
Total check, then reset the start whenever the tank goes negative. Proof in the worked section above.
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost):
return -1
tank, start = 0, 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
start, tank = i + 1, 0
return start
assert can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) == 3
assert can_complete_circuit([2, 3, 4], [3, 4, 3]) == -1
8. Two City Scheduling (LeetCode 1029) — Send half the people to each city at minimum cost.
Hint
Sort by ; first half to A. The adjacent-swap argument is in the worked section.
9. Partition Labels (LeetCode 763) — Cut a string into as many pieces as possible so that each letter appears in only one piece.
Hint
Record each letter's last index. Extend the current piece's end to the max last-index seen; cut when i equals it. This is interval merging in disguise.
10. Tasks and Deadlines (CSES 1630) — Each task has a duration and a deadline; reward is deadline minus finish time (can be negative). Maximise total reward.
Hint
Total reward . Deadlines are fixed, so minimise total completion time: shortest job first (adjacent-swap argument). Use 64-bit sums.
11. Task Scheduler (LeetCode 621) — Minimum slots with a cool-down.
Hint
. Be ready to explain the frames picture.
12. Candy (LeetCode 135) — Minimum candies with neighbour constraints.
Hint
Two passes, take the max. There is also an -space version that counts up and down slopes.
13. Stick Divisions (CSES 1161) — Cut a stick into given lengths; each cut costs the length of the piece being cut. Minimise total cost.
Solution
Run time backwards: cutting becomes merging, and merging two pieces costs their sum. That is Huffman's total cost — always merge the two smallest. With lengths 2, 3, 3: merge 2+3 = 5 (cost 5), then 5+3 = 8 (cost 8), total 13.
def stick_divisions(lengths):
heap = list(lengths)
heapq.heapify(heap)
cost = 0
while len(heap) > 1:
a = heapq.heappop(heap)
b = heapq.heappop(heap)
cost += a + b
heapq.heappush(heap, a + b)
return cost
assert stick_divisions([2, 3, 3]) == 13
14. Course Schedule III (LeetCode 630) — Courses have durations and last days; take as many as possible, one at a time.
Solution
Process courses by last day (EDF). Add each one; if the running time exceeds its last day, drop the longest course taken so far (a max-heap). Dropping the longest frees the most time while losing only one course — an exchange argument. Checked against brute force on 1,000 random inputs.
def schedule_course(courses):
heap, time = [], 0 # max-heap of durations (negated)
for dur, last_day in sorted(courses, key=lambda c: c[1]):
heapq.heappush(heap, -dur)
time += dur
if time > last_day: # over the deadline: drop the longest course so far
time += heapq.heappop(heap)
return len(heap)
assert schedule_course([[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]) == 3
assert schedule_course([[1, 2]]) == 1
assert schedule_course([[3, 2], [4, 3]]) == 0
15. Minimum Number of Refueling Stops (LeetCode 871) — Drive to a target past gas stations, stopping as few times as possible.
Hint
Drive as far as the fuel allows, pushing every station you pass into a max-heap. When you run dry, "retroactively" refuel at the biggest station passed. Greedy stays ahead: after stops you are as far as any -stop plan can be.
Common mistakes & interview follow-ups
"Prove your greedy is correct." Pick the technique, then do one swap concretely. For activity selection: "take any optimal set; replace its first activity by the earliest finisher; nothing it conflicts with is in the set, because everything else starts after the replaced one finished, which is no earlier." That is enough for most interviewers.
"Does it still work if intervals have weights?" No: counterexample with one long heavy interval vs two short light ones. Switch to the DP with binary search.
"What if the coins are 1, 3 and 4?" Greedy fails at 6. Offer the DP (dp[x] = 1 + min dp[x - c]), and mention that real currencies are canonical and that the smallest counterexample, if any, is below the sum of the two largest coins.
"Can Huffman be done without a heap?" Yes, if frequencies are sorted: two queues, .
"Why not shortest job first for max lateness?" Two jobs: , . SPT runs the 1-unit job first; the 10-unit job finishes at 11 and is 1 late. EDF runs it first and nobody is late.
"What changes with multiple machines?" Interval partitioning stays greedy. Minimising makespan on machines becomes NP-hard; LPT greedy is a -approximation.
"Jump game II in space-free — why is it BFS?" Because each window is exactly one BFS level of the implicit graph; no queue is needed because each level is contiguous.
Mistakes interviewers watch for: sorting by start instead of finish; > vs >= on touching intervals; claiming greedy works without a proof or a counterexample attempt; integer overflow in comparators and sums (Tasks and Deadlines needs 64-bit); forgetting the total-fuel check in gas station; giving a single Huffman symbol a 0-bit code.
Further Reading
- Dynamic Programming — when greedy fails, DP is usually the answer
- Graphs — MST algorithms in the context of graph theory
- Heaps & Priority Queues — the data structure powering Huffman and Prim's
- Advanced Data Structures — Union-Find used in Kruskal's
- Math Patterns in System Design — estimation and optimization in practice
- Intervals — merging, sweeping, rooms and the depth lower bound
- Minimum Spanning Trees — cut and cycle properties with full proofs
- Shortest Paths — Dijkstra as a greedy algorithm and why negative edges break it
- Union-Find — the structure behind Kruskal and deadline scheduling
- Randomized Algorithms — the next paradigm in this module
Sources
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — Chapter 15 "Greedy Algorithms" (activity selection, elements of the greedy strategy, Huffman codes, offline caching). The matroid sections (§16.4–16.5) are in the 3rd edition.
- Jon Kleinberg and Éva Tardos, Algorithm Design (2005) — Chapter 4: "greedy stays ahead", exchange arguments, interval scheduling and partitioning, minimising lateness, Huffman, MSTs.
- David A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE 40(9), 1952.
- Jack Edmonds, "Matroids and the greedy algorithm", Mathematical Programming 1, 1971; Richard Rado, "Note on independence functions", Proc. London Math. Soc., 1957. James Oxley, Matroid Theory (2nd ed., 2011) for the full theory.
- J. R. Jackson, "Scheduling a production line to minimize maximum tardiness", Research Report 43, UCLA, 1955.
- Dexter Kozen and Shmuel Zaks, "Optimal bounds for the change-making problem", Theoretical Computer Science 123, 1994; David Pearson, "A polynomial-time algorithm for the change-making problem", Operations Research Letters 33, 2005.
- P. Deutsch, RFC 1951: DEFLATE Compressed Data Format Specification, 1996 — §3.2.2 canonical Huffman codes.
- L. L. Larmore and D. S. Hirschberg, "A fast algorithm for optimal length-limited Huffman codes", JACM 37(3), 1990 (package-merge).
- C. L. Liu and J. W. Layland, "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment", JACM 20(1), 1973.
- cp-algorithms: Scheduling jobs on one machine.
Lessons: module — Paradigms · previous — Divide and Conquer · next — Bit Manipulation · course — DSA: Zero to Mastery.
Try It Yourself
Problem 1: Given activities with (start, finish) times: (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), select the maximum number of non-overlapping activities.
Solution
Sort by finish time: (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11). Greedy: always pick the activity with the earliest finish time that does not overlap:
- Pick (1,4). lastFinish=4.
- Skip (3,5): start 3 < 4.
- Skip (0,6): start 0 < 4.
- Pick (5,7): start 5 >= 4. lastFinish=7.
- Skip (3,9), (5,9), (6,10): starts < 7.
- Pick (8,11): start 8 >= 7. Answer: 3 activities: (1,4), (5,7), (8,11).
Problem 2: Given items with (weight, value): (10, 60), (20, 100), (30, 120) and knapsack capacity 50, solve the fractional knapsack.
Solution
Calculate value/weight ratios: 60/10=6, 100/20=5, 120/30=4. Sort by ratio descending: (10,60,ratio=6), (20,100,ratio=5), (30,120,ratio=4).
- Take item 1 entirely: weight=10, value=60. Remaining=40.
- Take item 2 entirely: weight=20, value=100. Remaining=20.
- Take 20/30 of item 3: value = 120 * (20/30) = 80. Total value: 60 + 100 + 80 = 240.0
Problem 3: Given intervals [(0,30), (5,10), (15,20)], find the minimum number of meeting rooms required.
Solution
Sort by start time: (0,30), (5,10), (15,20). Use a min-heap of end times:
- (0,30): heap=[30], rooms=1
- (5,10): 5 < 30, need new room. heap=[10, 30], rooms=2
- (15,20): 15 >= 10, reuse room. heap=[20, 30], rooms=2 Answer: 2 rooms
Problem 4: Show that greedy fails for the coin change problem with denominations [1, 3, 4] and target 6.
Solution
Greedy approach (largest coin first):
- Take 4 (remaining: 2)
- Take 1 (remaining: 1)
- Take 1 (remaining: 0)
- Total: 3 coins (4 + 1 + 1)
Optimal approach:
- Take 3 + 3 = 2 coins
Greedy fails because taking the largest coin first blocks a better combination. The greedy choice property does not hold for arbitrary coin denominations.
Problem 5: Use Kruskal's algorithm to find the MST of a graph with edges: (A,B,4), (A,C,8), (B,C,11), (B,D,8), (C,D,7), (C,E,1), (D,E,2).
Solution
Sort edges by weight: (C,E,1), (D,E,2), (A,B,4), (C,D,7), (A,C,8), (B,D,8), (B,C,11). Process with Union-Find:
- (C,E,1): add. Components: {A},{B},{C,E},{D}
- (D,E,2): add. Components: {A},{B},{C,D,E}
- (A,B,4): add. Components: {A,B},{C,D,E}
- (C,D,7): C and D already connected. Skip.
- (A,C,8): add. All connected. MST edges: (C,E,1), (D,E,2), (A,B,4), (A,C,8). Total weight: 15.
Quick Quiz
1. What two properties must a problem have for a greedy algorithm to produce an optimal solution?
- a) Overlapping subproblems and optimal substructure
- b) Greedy choice property and optimal substructure
- c) Divide and conquer structure and greedy choice property
- d) Polynomial time and greedy choice property
Answer
b) Greedy choice property and optimal substructure — The greedy choice property means a locally optimal choice leads to a globally optimal solution. Optimal substructure means the optimal solution contains optimal solutions to subproblems.
2. Why does greedy work for the fractional knapsack but not for the 0/1 knapsack?
- a) Fractional knapsack has fewer items
- b) In fractional knapsack you can take parts of items, so the highest-ratio item is always worth taking; in 0/1 you must take whole items, and a high-ratio item may waste capacity
- c) 0/1 knapsack is NP-hard
- d) Greedy works for both
Answer
b) In fractional knapsack you can take parts of items, so the highest-ratio item is always worth taking; in 0/1 you must take whole items, and a high-ratio item may waste capacity — Taking fractions ensures you never "waste" capacity, making the greedy choice (best ratio) always optimal. With whole items, a high-ratio item may leave capacity that could have been better filled by a different combination.
3. In Kruskal's MST algorithm, how are cycles detected?
- a) BFS
- b) DFS
- c) Union-Find (Disjoint Set Union)
- d) Adjacency matrix lookup
Answer
c) Union-Find (Disjoint Set Union) — Before adding an edge , check if and are already in the same set using find(). If they are, adding the edge would create a cycle.
4. What is the time complexity of Huffman coding for characters?
- a)
- b)
- c)
- d)
Answer
b) — Building the initial heap takes . Extracting and inserting into the heap happens times, each taking , giving overall.
5. How do you formally prove that a greedy algorithm is correct?
- a) Run it on several test cases
- b) Use an exchange argument: show that any optimal solution can be modified to include the greedy choice without worsening it
- c) Compare it to the brute-force solution
- d) Prove it runs in polynomial time
Answer
b) Use an exchange argument: show that any optimal solution can be modified to include the greedy choice without worsening it — The exchange argument takes an arbitrary optimal solution and shows you can swap out a non-greedy choice for the greedy choice without losing optimality, proving the greedy strategy is correct.