Greedy problems — activity selection, fractional knapsack, Huffman coding (full algorithm): Worked examples

This page hammers the three greedy algorithms from the parent topic against every kind of input they can meet: nice inputs, ties, zero/degenerate inputs, and the traps where greedy breaks. Read the matrix first, then each worked example tells you which cell it covers.

The scenario matrix

#	Topic	Case class	What could go wrong	Example
C1	Activity Selection	Ties in finish time	which of two equal-finishers do we take?	Ex 1
C2	Activity Selection	Touching intervals (start == last finish)	is " $\geq$ " or " $>$ " correct?	Ex 2
C3	Activity Selection	Degenerate: 0 or 1 activity	does the loop still work?	Ex 3
C4	Fractional Knapsack	Everything fits (no fraction needed)	greedy must not "over-cut"	Ex 4
C5	Fractional Knapsack	Density tie + real-world words	tie-breaking is irrelevant, prove it	Ex 5
C6	Fractional Knapsack	0/1 twist — indivisible items	greedy density fails; DP wins	Ex 6
C7	Fractional Knapsack	Zero capacity / zero-weight item	division by zero, empty bag	Ex 7
C8	Huffman	All frequencies equal	tree becomes balanced	Ex 8
C9	Huffman	Merge ties / heap order	exam twist: recompute cost	Ex 9
C10	Huffman	Single symbol (degenerate)	codeword length must be 1, not 0	Ex 10

Part A — Activity Selection

Worked example Ex 1 — Cell C1: two activities finish at the same time

Activities (start, finish): P(1,4) Q(2,4) R(4,7) S(5,8).

Forecast: P and Q both finish at 4. Does it matter which we keep? Guess the final set size.

Sort by finish. Order: P(1,4), Q(2,4), R(4,7), S(5,8) — P and Q tie at 4. Why this step? Earliest-finish is the safe greedy key; ties can be broken arbitrarily because both leave last = 4.
Pick the first (say P). last = 4. Why this step? Whichever of P, Q we pick, the future window "start $\geq 4$ " is identical — the tie is harmless.
Scan: Q start $2 < 4$ ✗. R start $4 \geq 4$ ✓ → pick, last = 7. Why this step? R is the first compatible activity after our pick.
S start $5 < 7$ ✗. Done. Result {P, R}, size 2.

Verify: Had we picked Q instead of P, we still get {Q, R}, size 2 — same count. Ties never change the optimum size. ✓

Worked example Ex 2 — Cell C2: intervals that just touch

Activities: U(1,3) V(3,5) W(5,6). Every activity starts exactly when the previous ends.

Forecast: are "touching" activities compatible? Predict: can we take all three?

The compatibility test is start >= last_finish. Why this step? An activity that starts at the same instant another finishes does not overlap — the resource is free at that boundary. This is why we use $\geq$ , not $>$ .
Sort by finish (already sorted). Pick U, last = 3.
V start $3 \geq 3$ ✓ → pick, last = 5. W start $5 \geq 5$ ✓ → pick. Why this step? Each start meets the previous finish exactly, so all pass the $\geq$ test.
Result {U, V, W}, size 3.

Verify: No two chosen intervals share an interior point; boundaries touch but don't overlap. If your problem defines overlap as "sharing even the endpoint," you'd switch to $>$ and get size 2 instead — know your definition. ✓

Part B — Fractional Knapsack

Worked example Ex 4 — Cell C4: everything fits, no cut needed

Capacity $W = 100$ . Items: $A (v = 30, w = 20)$ , $B (v = 40, w = 30)$ , $C (v = 10, w = 10)$ .

Forecast: total weight is $20 + 30 + 10 = 60 \leq 100$ . Do we ever take a fraction?

Densities: $d_{A} = 30/20 = 1.5$ , $d_{B} = 40/30 \approx 1.333$ , $d_{C} = 10/10 = 1.0$ . Why this step? Density $v_{i} / w_{i}$ is the value of one kilogram of slot — always the greedy key.
Sort descending: $A, B, C$ . Take $A$ whole (room $100 \to 80$ , value 30), $B$ whole (room $80 \to 50$ , value 70), $C$ whole (room $50 \to 40$ , value 80). Why this step? Each item fits entirely, so $x_{i} = 1$ ; a fraction is only forced when an item overflows.
Room $40$ left, no items remain. Total value 80.

Verify: $30 + 40 + 10 = 80$ ; total weight used $60 \leq 100$ . Since all items fit, we took everything — the bag isn't even full, and that's optimal (no leftover item to add). ✓

Worked example Ex 5 — Cell C5: density tie + word problem

A juice bar bag holds $W = 5$ litres. Three syrups: Mango (₹90, 3 L), Berry (₹60, 2 L), Lime (₹150, 5 L). Maximise rupee value; you may pour fractions.

Forecast: compute the price-per-litre of each — two of them tie. Does the tie change the answer?

Densities (₹/L): Mango $90/3 = 30$ , Berry $60/2 = 30$ , Lime $150/5 = 30$ . All tie at ₹30/L. Why this step? Density is the per-litre price; equal densities mean it does not matter which syrup fills the bag.
Since every litre is worth ₹30 regardless of source, fill the bag any way: 5 L total → value $5 \times 30 = ₹150$ . Why this step? With equal density the Exchange Argument gives zero change when swapping — every choice is optimal.
E.g. take all Mango (3 L) + 1 L Berry (₹30) + 1 L Lime (₹30): $90 + 30 + 30 = ₹150$ .

Verify: $150 = 5 L \times ₹30/ L$ . Any mix hitting exactly 5 L gives ₹150. Ties are harmless — same total. ✓

Worked example Ex 6 — Cell C6: the 0/1 twist where greedy FAILS

Same items as the parent's counterexample, but items are indivisible (0/1 knapsack): $W = 50$ , $A (60, 10)$ , $B (100, 20)$ , $C (120, 30)$ .

Forecast: greedy-by-density took $A, B$ then $\frac{2}{3} C = 80$ for a fractional value of 240. But if you cannot cut $C$ , what does density-greedy give, and is it optimal? Guess before reading.

Density order: $d_{A} = 6, d_{B} = 5, d_{C} = 4$ → try $A, B, C$ . Why this step? This is exactly the greedy rule — we test it on indivisible items.
Take $A$ (w 10, room $50 \to 40$ ), take $B$ (w 20, room $40 \to 20$ ). Now $C$ weighs 30 $>$ 20 — cannot cut it, so skip. Greedy value $= 60 + 100 =$ 160. Why this step? No fractions allowed → the overflowing item is dropped entirely, leaving a wasted gap of 20.
Optimal (by Dynamic Programming): try $B + C = 100 + 120 =$ 220 (weight $20 + 30 = 50$ , fits exactly). Why this step? DP considers skipping the densest item $A$ to fit two heavier-but-larger-total items — greedy never reconsiders, so it misses this.

Verify: greedy 160 $<$ optimal 220. Density-greedy is wrong for 0/1; the fractional answer (240) is an unreachable upper bound. Lesson: fractions are exactly what make greedy safe. ✓

Worked example Ex 7 — Cell C7: zero capacity and a zero-weight item

Case (a): $W = 0$ with any items. Case (b): $W = 10$ and an item $Z (v = 50, w = 0)$ (a "free" item, zero weight) plus $A (v = 20, w = 10)$ .

Forecast: what is $d_{Z} = v_{Z} / w_{Z}$ ? What does the algorithm do?

$W = 0$ : no room for anything, every $x_{i} = 0$ , total value 0. Why this step? An empty bag can hold nothing — the loop takes nothing.
Zero-weight item $Z$ : $d_{Z} = 50/0$ is undefined (infinite density) — pure value at no weight cost. Why this step? You must special-case $w_{i} = 0$ : such an item is always taken whole for free before sorting, since it never consumes capacity.
Take $Z$ (value 50, room unchanged 10), then $A$ whole (value 20, room $10 \to 0$ ). Total 70.

Verify: $50 + 20 = 70$ ; weight used $= 0 + 10 = 10 \leq 10$ . Guarding division-by-zero and grabbing free items first is mandatory for robust code. ✓

Part C — Huffman Coding

The next examples use a code-tree picture; the merge order is the whole story.

Figure — Greedy problems — activity selection, fractional knapsack, Huffman coding (full algorithm)

Worked example Ex 8 — Cell C8: all frequencies equal → balanced tree

Four symbols each with frequency 1: a:1, b:1, c:1, d:1.

Forecast: with equal frequencies, what shape is the tree? Guess the codeword lengths.

Min-heap: [1,1,1,1]. Pop two smallest (a,b) → merge to 2. Heap: [1,1,2]. Why this step? Huffman always merges the two minimums; here all are equal so the pair choice is arbitrary.
Pop (c,d) → merge to 2. Heap: [2,2].
Pop (2,2) → merge to 4 = root. Heap: [4]. Why this step? Last node is the root; three merges for four leaves ( $n - 1 = 3$ ).
Tree is balanced: every leaf at depth 2 → every codeword length 2.

Verify (cost identity): total bits $=$ sum of internal-node frequencies $= 2 + 2 + 4 =$ 8. Direct check: $4 symbols \times 1 \times 2 bits = 8$ ✓. Equal frequencies ⇒ Huffman degenerates to a fixed-length code, exactly as expected.

Worked example Ex 9 — Cell C9: merge ties, exam-style cost twist

Symbols: a:2, b:2, c:3, d:7.

Forecast: there is a tie (two 2's, and a 4 could tie a 3-family). Compute the total encoded length.

Heap [2,2,3,7]. Pop a(2), b(2) → merge 4. Heap: [3,4,7]. Why this step? The two smallest are the pair of 2's; tie-break between the equal 2's doesn't affect cost.
Pop 3(c), 4(ab) → merge 7. Heap: [7,7]. Why this step? Now 3 and 4 are the two smallest; note 7 (=merge) ties with d:7 but that's next round.
Pop 7, 7 → merge 14 = root. Heap: [14].
Lengths: d is one edge from root → length 1. c is two edges → length 2. a, b are three edges → length 3.

Verify (two ways):

Cost identity: internal nodes $4 + 7 + 14 =$ 25 bits.
Direct: $2 (3) + 2 (3) + 3 (2) + 7 (1) = 6 + 6 + 6 + 7 =$ 25 ✓. Both agree — the tie in the heap did not change the minimum cost.

Worked example Ex 10 — Cell C10: single symbol (degenerate)

One symbol: a:12. Encode a message of all a's.

Forecast: Huffman's loop runs $n - 1 = 0$ times. What codeword does a get — length 0?

Only one symbol → no merges happen (the min-heap has a single node). Why this step? With $n = 1$ , the "pop two" step can never run; the loop body executes 0 times.
A codeword of length 0 is illegal — you couldn't tell one a from two. Why this step? Prefix codes need at least one bit per symbol when there is anything to send.
Special-case fix: assign a the single-bit codeword 0 (length 1). Why this step? Standard implementations force length $\geq 1$ for the lone symbol.

Verify: cost $= 12 \times 1 =$ 12 bits (one bit per occurrence). The theoretical entropy of a certain source is 0, but real encoders must still emit $\geq 1$ bit/symbol — the degenerate case that pure information theory hides. ✓

Recall Which cell did each example fix?

Ties in finish time — harmless? ::: Yes — both equal finishers leave the same future window (Ex 1). Do touching intervals overlap under start >= last? ::: No — boundary contact is allowed (Ex 2). Does density-greedy solve 0/1 knapsack? ::: No — Ex 6 gives 160 vs optimal 220; use DP. Huffman with all-equal frequencies gives what tree? ::: A balanced fixed-length tree (Ex 8). Codeword length for a single-symbol alphabet? ::: 1 (never 0), by special case (Ex 10).

Related tools used above: Priority Queue / Binary Heap (Huffman merges), Sorting Algorithms (finish-time / density sort), Exchange Argument (why each greedy pick is safe), Dynamic Programming (the 0/1 fallback), Minimum Spanning Tree (Kruskal/Prim) (another exchange-argument greedy).