Greedy Algorithms

By the end of this lesson you will be able to trace the activity-selection problem from its dynamic-programming roots through recursiveActivitySelector and greedyActivitySelector; state and use the greedy-choice property and optimal substructure to tell when a greedy algorithm is even allowed; build a Huffman tree by hand from a min-priority queue and read off its codewords and bit cost; recognise a matroid and run the generic matroidGreedy algorithm on it (spanning forests, task scheduling); and — just as importantly — construct and explain the classic cases where greedy FAILS (0/1 knapsack, coin changing with denominations {1, 5, 8}).

This lesson assumes you're comfortable with Dynamic Programming: greedy algorithms are best understood as a SPECIAL, faster case of problems that also have optimal substructure — the same property DP relies on — but where you additionally get to skip solving all the subproblems, because one particular first choice is provably always safe.

1. The activity-selection problem & optimal substructure

You run ONE lecture hall (or one meeting room, or one machine). n people each want it for an interval [s_i, f_i) — starting at s_i, finishing at f_i. Two requests are compatible if their intervals don't overlap. You want the MAXIMUM number of requests you can satisfy. This is the running example for this whole lesson — assume the activities are already sorted so f₁ ≤ f₂ ≤ ... ≤ f_n.

An 11-activity example (activities numbered 0 to 10), already sorted by finish time — you'll see this exact set animated below:

Optimal substructure: define fits(p, q) = the activities that start after activity p finishes and finish before activity q starts. If some activity k in fits(p, q) belongs to an optimal solution, that solution splits into an optimal solution for fits(p, k), the activity k itself, and an optimal solution for fits(k, q); a cut-and-paste argument (swap in a better sub-answer and the whole thing improves, a contradiction) shows each part must be optimal for its own subproblem. This gives the naive DP recurrence:

The same recurrence as Dart (two sentinel positions frame the real activities: one that finishes at time 0 before everything, one that starts at infinity after everything), counting its inner-loop steps:

Input size → what’s feasible: this table needs C(n+2, 3) ≈ n³/6 inner steps: n = 80 → 88,560 (instant), n = 1,000 → ≈ 1.7·10⁸ (about a second), n = 10⁵ → 1.7·10¹⁴ (never). Hence the next section's shortcut.

So far this is ORDINARY dynamic programming — exactly the shape of the previous lesson's problems, with a table indexed by pairs (i,j). What makes activity selection special is the earliest-finish rule in Section 2: one specific choice is ALWAYS safe, which collapses the two-dimensional DP down to zero tables at all.

2. recursiveActivitySelector & the greedy-choice property

The earliest-finish rule: among the activities still available, the one that finishes EARLIEST is always part of SOME optimal solution. Intuition: finishing early leaves the most room on the clock for everything that comes after — there is never a reason to prefer a later finish time for your first pick.

This means only ONE subproblem ever remains after the greedy choice — not the many subproblems a generic DP recurrence would suggest. recursiveActivitySelector(s, f, k, n) makes this concrete (0-indexed like Dart; k is the last activity chosen, and the first call uses k = −1 to mean “nothing chosen yet”, with finish time 0):

Proof of the earliest-finish rule (swap argument): suppose an optimal solution's earliest-finishing member is a_j ≠ a_m (where a_m is the truly earliest-finishing activity available). Since a_m finishes at or before a_j, swapping a_j out for a_m cannot break compatibility with anything else in the solution, and the solution stays the same SIZE — so it's still optimal, and now contains a_m. This is the same "exchange argument" pattern used throughout this lesson (Huffman's leaf-swap lemma, the matroid greedy-choice lemma).

The earliest-finish rule as code: enumerate EVERY compatible subset of the 11 activities, take each maximum one, apply the swap, and check it stays compatible, keeps its size and now contains activity 0 (the earliest finisher):

Edge case: what happens when several activities are fully overlapping, so only ONE of them can ever be chosen?

Try your own set of activities on the recursive version itself (format start-finish, comma-separated — sorted by finish time automatically):

recursiveActivitySelector runs in Θ(n) time — each activity is examined at most once across the whole recursion (the pointer m only ever moves forward), even though the recursion looks like it could revisit work.

Dart implementation (a tiny finishOf(k) helper treats k < 0 as “finish time 0”, so the first call can say “nothing chosen yet” with k = −1; the loop bound is m < n because the last valid index is n − 1):

Input size → what’s feasible: n ≤ ~10⁴ sorted activities → this recursive version is fine (the recursion depth equals the number of activities picked, so at most n frames); for n beyond a few 10⁴, or when you cannot risk a stack overflow, use the loop in the next section.

3. greedyActivitySelector (iterative)

The recursive version is “tail recursive” — the recursive call is the very last thing that happens — so it converts mechanically into a simple loop, greedyActivitySelector(s, f):

Edge case: every activity finishes at the SAME time (all fully overlap) — only one can ever be picked, no matter how many there are:

Try your own set of activities (format start-finish, comma-separated — they'll be sorted by finish time automatically, exactly as greedyActivitySelector requires):

greedyActivitySelector silently assumes the input is ALREADY sorted by finish time. Feed it activities in start-time order (or any other order) without sorting first and it will happily return a WRONG, non-maximum answer — the algorithm has no way to detect that its precondition was violated.

greedyActivitySelector: Θ(n) time given pre-sorted input (or Θ(n lg n) if you must sort first), O(1) extra space, always returns a MAXIMUM-size compatible subset (not necessarily the only one — the example above has other equally-sized answers such as {a1, a4, a9, a10}).

Dart implementation (the first activity, index 0, is always chosen, so A = [0] and k = 0; the loop then scans m = 1 … n − 1):

Input size → what’s feasible: n = 10⁶ activities already sorted by finish time → one pass = n − 1 ≈ 10⁶ comparisons (milliseconds); if they arrive unsorted, sort first: n lg n ≈ 2·10⁷ steps, still well under a second.

The Θ(n) claim and the unsorted-input pitfall, both as running code (greedyComparisons counts one comparison per activity; the pitfall input is (0,10), (1,2), (4,5) in START order):

4. Elements of the greedy strategy

Sections 1 to 3 followed a careful 6-step derivation (optimal substructure → DP recurrence → show the greedy choice leaves ONE subproblem → prove it's safe → recursive greedy algorithm → convert to a loop). In practice, once you trust the pattern, a shorter 3-step process is enough for a new problem:

Cast the problem as "make one choice, then solve one remaining subproblem" — not many subproblems.
Prove the greedy-choice property: show SOME optimal solution contains your proposed first choice (an exchange argument, as in the earliest-finish proof).
Show optimal substructure: greedy choice + an optimal solution to what's left ⇒ an optimal solution overall.

The crucial contrast with DP: DP solves ALL the subproblems first, THEN combines them (bottom-up) — it doesn't know in advance which choice will turn out best. Greedy makes its choice FIRST, top-down, with NO backtracking and NO lookahead, and only afterwards recurses into whatever single subproblem remains. This is only safe when the greedy-choice property has actually been proven — Section 5 shows what happens when it hasn't.

Greedy versus the DP of Section 1, on the same inputs: the DP table work grows like n³/6, the greedy loop like n.

5. Fractional vs. 0/1 knapsack — when greedy fails

A thief has a knapsack that holds weight W. There are n items, each with a weight w_i and a value v_i. In the fractional version the thief can cut items into pieces (think gold dust, olive oil); in the 0/1 version each item is indivisible — take the whole thing or leave it (think a painting, a stereo).

The natural greedy idea for both: sort items by value-per-pound v_i/w_i, descending, then grab as much as you can starting from the best ratio.

Why fractional greedy is exactly optimal: suppose an optimal solution does NOT fully take the highest-ratio item first. Swapping in a tiny extra amount of it for an equal WEIGHT of some lower-ratio item already in the knapsack strictly increases total value without changing total weight — contradicting optimality. So the highest-ratio item must be taken as fully as capacity allows; induct on the rest.

The exchange argument above as arithmetic (eps kilograms move from the lower-ratio item to the higher-ratio one):

Try your own items and capacity (format name:weight:value, comma-separated):

Dart implementation of fractional knapsack (the shape mirrors greedyActivitySelector: sort, then walk once):

Input size → what’s feasible: n = 10⁵ items → the sort costs n lg n ≈ 1.7·10⁶ steps (fine); a selection-based method removes the sort for an O(n) running time (see the Expert questions).

Now run the EXACT SAME greedy-by-ratio idea on the 0/1 version of the identical instance — items can only be taken whole:

This is the headline counterexample. Greedy-by-ratio takes Saffron first (best ratio), then Cocoa, and then Tea no longer fits. But the TRUE optimum skips Cocoa entirely and takes Saffron + Tea. Both problems have optimal substructure — the difference is that 0/1 knapsack has overlapping subproblems (whether the first item is "available" affects every later decision in a way that can't be resolved by one irrevocable up-front choice), which is exactly DP territory (an O(nW) DP table solves it exactly, shown in the Interview questions section below).

All three algorithms as Dart, on this lesson’s instance (weights 8, 15, 22; values 48, 75, 88; W = 30). Ratios are compared by cross-multiplying (v[b]*w[a] vs v[a]*w[b]) so no floating-point division is needed:

Fractional knapsack: greedy by value/weight ratio, O(n lg n), PROVABLY optimal. 0/1 knapsack: the same greedy heuristic can be arbitrarily far from optimal — you need dynamic programming instead. Same-looking problem, one word ("fractional") away from a totally different algorithmic answer.

6. Huffman codes

You want to compress a file. Fixed-width codes (every character gets, say, 3 bits) waste space on common characters. A prefix code assigns SHORT codewords to frequent characters and LONG codewords to rare ones, while guaranteeing no codeword is a PREFIX of another — which is exactly what makes the encoded bit-stream unambiguous to decode, one bit at a time, with no separators needed. A prefix code is exactly a binary tree: go left on a 0, right on a 1, and every character sits at a LEAF.

Cost of a tree T: B(T) = ∑ c.freq × d_T(c) — frequency times codeword length (depth), summed over every character c. buildHuffmanTree builds the optimal tree bottom-up using a min-priority queue Q keyed on frequency:

The worked example is a text over a 6-letter alphabet, with frequencies given as counts per 100 symbols: m:38, k:22, p:15, r:12, x:8, z:5 (38+22+15+12+8+5 = 100). The animation below computes a tree cost of 237 bits per 100 symbols, versus 300 bits for a fixed 3-bit-per-symbol code (⌈lg 6⌉ = 3 bits × 100 symbols) — a saving of about 21%. Scale the counts by 1,000 and it is 237,000 bits instead of 300,000 for a 100,000-symbol file.

The cost formula B(T) = ∑ c.freq · d_T(c) as code, together with the second way to count it (each merge adds its combined frequency once):

Greedy-choice lemma: the two LOWEST-frequency characters can always be made siblings at MAXIMUM depth in some optimal tree — an exchange argument (swap them into place; since they have the smallest frequencies, this swap can only decrease or keep the same total cost). Optimal-substructure lemma: once those two are merged into one combined-frequency "character" z, an optimal tree for the smaller alphabet C - {x,y} + {z}, with z's leaf expanded back into an internal node with children x,y, is optimal for the original alphabet C. Together these prove Huffman's algorithm is correct — the exact same greedy-choice-plus-optimal-substructure pattern as activity selection, just with a priority queue standing in for "always pick the finish-time minimum."

The exchange step of the greedy-choice lemma as code: swapping two leaves changes B(T) by exactly (f_x − f_y)(d_x − d_y), so moving the frequent letter up and the rare letter down can only help:

Edge cases: what does the tree look like with only 2 characters, or with several characters at EXACTLY EQUAL frequency?

Try your own alphabet (format char:freq, comma-separated, 2–7 distinct characters):

Huffman: O(n lg n) time with a binary min-heap (n-1 merges × O(lg n) per removeMin/add). Produces a full binary tree (every internal node has exactly 2 children — a node with one child could be spliced out to shorten codewords). All optimal trees for the same frequencies share the SAME total cost B(T), even if individual codewords differ.

Dart implementation (a sorted List<HuffNode> stands in for a binary min-heap: a moving head index plays removeMin and insert plays add):

Input size → what’s feasible: alphabet of n = 256 byte values → trivial; n = 10⁵ distinct words → this sorted-list version costs O(n) per merge = 10¹⁰ (too slow), so use a real heap or the sort-once two-queue method (O(n lg n), interview question “Build a full Huffman code”).

7. Matroids & the GREEDY algorithm

Activity selection and Huffman coding each needed their OWN custom proof. A matroid is the abstract structure that lets us prove, ONCE, that a generic greedy algorithm is correct for EVERY problem that happens to fit the pattern — most famously, minimum/maximum spanning trees.

The three matroid conditions as running code, on the graphic matroid of a triangle (edges 0, 1, 2) plus a pendant edge 3. Subsets are bit masks, independence = “no cycle”. It checks the empty set, heredity, the exchange property, and the equal-size property (every maximal independent set has |V| − 1 = 3 edges):

The graphic matroid M_G = (S_G, ℑ_G) for an undirected graph G=(V,E): the ground set is the edges, and a set of edges is "independent" exactly when it's ACYCLIC (forms a forest). A short argument (see the Expert questions) proves this really is a matroid, and it follows that every MAXIMAL independent set (here: every spanning tree) has the same size, |V|-1.

The generic algorithm, specialised to a WEIGHTED matroid (build the maximum-weight independent set):

Edge case: a graph that is a single TRIANGLE, with all three edges TIED at the same weight — must GREEDY still reject one, no matter how the tie is broken?

Try your own weighted edge list (format u-v-w, comma-separated, plus the number of vertices):

Greedy-choice property for matroids: if x is the first element (by decreasing weight) with {x} ∈ ℑ, some optimal (maximum-weight independent) set contains x — another exchange argument, using the matroid EXCHANGE PROPERTY itself to swap x in for some no-heavier element. A contraction lemma then shows the rest of the problem reduces to the SAME kind of problem on a smaller, "contracted" matroid — so matroidGreedy is always correct on any matroid, with no problem-specific proof needed.

The generic matroidGreedy itself, written once against an independence oracle (any matroid plugs in), shown with the graphic matroid on the page’s 5-vertex example:

matroidGreedy: O(n lg n) sort + n independence checks. For the graphic matroid this specialises to exactly Kruskal's minimum/maximum-spanning-tree algorithm — a union-find independence test in place of a generic ℑ membership test.

Dart implementation (vertices numbered 0..|V|-1, so a plain List<int> parent array works for the union-find independence test; sorting is DESCENDING here because we're building a MAXIMUM-weight forest, the mirror image of the minimum-spanning-tree version):

Input size → what’s feasible: V = 10⁵ vertices, E = 2·10⁵ edges → sort E lg E ≈ 3.6·10⁶ steps plus E near-constant union-find calls (fast); the generic oracle version above re-checks the whole set each time (O(n) per test), so it is for understanding, not for n = 10⁵.

8. Task scheduling as a matroid

You have n unit-time tasks (each takes exactly 1 time slot), each with a deadline d_i (an integer, 1 ≤ d_i ≤ n) and a penalty w_i you must pay if the task finishes LATE. You want to schedule tasks (one at a time, one slot each) to MINIMIZE the total penalty of the late ones — equivalently, to MAXIMIZE the total penalty saved by the ON-TIME ("early") tasks.

The on-time counting rule: a set of tasks A can ALL be scheduled on time if and only if, for every t = 0..n, N_t(A) ≤ t, where N_t(A) counts tasks in A with deadline ≤ t. This "independence" relation is a matroid (see the Expert questions), so the matroid greedy-choice property from Section 7 applies directly: run GREEDY, ordering tasks by DECREASING penalty.

The counting rule as code (the independence test N_t(A) ≤ t), plugged into the generic matroidGreedy from Section 7 on this lesson’s 7-task example:

Edge case: what happens when EVERY task shares the exact same deadline?

Try your own tasks (format deadline:penalty pairs, comma-separated):

A simple O(n²) implementation: process tasks by decreasing penalty, and place each one in the LATEST still-free slot at or before its deadline (rejecting it — "late" — only if every slot up to its deadline is already full). A disjoint-set forest speeds this up to near-linear by finding the latest free slot in close to O(1) amortized time (see the Expert questions).

Dart implementation (a deadline is a time between 1 and n, meaning “finish by the end of minute d”; the slot list is 0-indexed, so slot[s] is the task running during minute s + 1, and math.min(n, deadline) - 1 is the last slot index a task may use):

Input size → what’s feasible: n = 1,000 tasks → the O(n²) latest-free-slot scan is 10⁶ steps (fine); n = 10⁵ → 10¹⁰ (too slow), so use the disjoint-set version (Expert question).

9. Coin changing — another counterexample

Give change for an amount using the FEWEST coins from a set of denominations. With everyday coins (say, 25/10/5/1) the greedy rule "always take the largest coin that fits" happens to be optimal — this denomination set is called canonical. But greedy is NOT a theorem about coin systems in general.

A small counterexample: denominations {1, 5, 8}, amount = 10.

Greedy has no way to "look ahead" and see that grabbing the 4 now will force two more small coins later. There is no known simple characterization that tells you IN ADVANCE whether a denomination set is canonical (proving it for a specific set can itself be a research-level exercise) — so production code should use the DP below, never assume greedy works.

Try your own denominations and target amount — the animation always runs the safe DP alongside greedy and tells you whether they agree:

Coin changing DP: O(n · amount) time, ALWAYS exact and optimal, for ANY denomination set (even ones without a coin of value 1, where some amounts become simply impossible). Greedy is O(n) but only correct for canonical systems — and you often can't easily tell in advance whether your denominations are canonical.

Greedy and DP coin changing as code, plus a tester that finds the first amount where greedy is not optimal ({1,5,8} fails at 10, {1,6,10} at 12, US coins never up to 500):

Input size → what’s feasible: amount ≤ 10⁵ with at most 12 denominations → DP = 1.2·10⁶ steps (instant); greedy is O(n) but only valid for canonical sets, and proving a set canonical in general is not something to do at run time.

Quiz

Interview questions

Cheat sheet

Algorithm	Time	Space	Optimal?	When to use
recursiveActivitySelector / greedyActivitySelector	Θ(n) after sort, Θ(n lg n) total	O(1) extra (iterative)	Yes (earliest-finish rule)	Max # of non-overlapping intervals; input MUST be sorted by finish time
Weighted activity selection	O(n²) (O(n lg n) with binary search for p(i))	O(n)	Yes (DP, not plain greedy)	Same as above but maximizing total VALUE, not count
Fractional knapsack	O(n lg n)	O(n)	Yes (exchange argument)	Items can be split (money, weight of a commodity)
0/1 knapsack — greedy by ratio	O(n lg n)	O(1)	No — counterexample in §5	Never use for 0/1; use the O(nW) DP instead
0/1 knapsack — DP	O(nW)	O(nW) (O(W) rolling)	Yes	Items indivisible, small integer capacity W
buildHuffmanTree	O(n lg n) with a binary heap	O(n)	Yes (greedy choice + substructure)	Build an optimal prefix code from character frequencies
matroidGreedy on a matroid	O(n lg n + n·f(n)), f(n)=cost of one independence check	O(n)	Yes, but only ON a matroid	Max/min spanning forest, task scheduling, anything provably matroid-shaped
Task scheduling (latest-free-slot greedy)	O(n²) simple, ~O(n α(n)) with disjoint sets	O(n)	Yes (it is a matroid)	Unit-time tasks, deadlines, minimize total penalty of late ones
Coin changing — greedy	O(n) per amount	O(1)	Only for CANONICAL denominations	US-style coins; never trust blindly on arbitrary denominations
Coin changing — DP	O(n · amount)	O(amount)	Always	Any denomination set, safe default