Classic greedy algorithms

Fractional knapsack, interval problems, and Huffman coding. · 11 min read

Fractional knapsack

Unlike 0/1 knapsack, here you may take fractions of items. Greedy is optimal: sort by value/weight ratio and take as much of the best ratio as fits, then the next, splitting the last item to fill the bag exactly.

sort(items, by value/weight descending);
double total = 0; int cap = W;
for (auto& it : items) {
    if (it.weight <= cap) { total += it.value; cap -= it.weight; }
    else { total += it.value * (double)cap / it.weight; break; }
}

Interactive visualization: Fractional knapsack: fill by value/weight ratio — step through it frame by frame on this page.

Interval problems

A whole family of problems yields to "sort by an endpoint, then sweep": interval scheduling (max non-overlapping, sort by finish), minimum arrows / point cover (sort by end, shoot at each end), merge intervals (sort by start), and minimum rooms (sort starts and ends, sweep a counter). The trick is choosing which endpoint to sort by.

Huffman coding

To compress symbols by frequency, Huffman's algorithm repeatedly merges the two least-frequent nodes into a parent (with a min-heap), building an optimal prefix-free code bottom-up. Rare symbols get longer codes, frequent ones shorter — provably minimal total encoded length. It's greedy + a priority queue.

Huffman builds an optimal prefix code

Pop the two smallest frequencies. — A min-heap gives them in O(log n).
Merge them into a node of summed frequency; push it back. — Repeat until one tree remains.
Left/right edges = bits 0/1; depth = code length. — Frequent symbols stay shallow.

Result: O(n log n)

Practice: Minimum Arrows to Burst Balloons (Hard) — Fewest points that stab every interval — a greedy sweep.