Task Scheduling

Huffman Coding

Build an optimal prefix code for data compression. Always merge the two least frequent symbols into one node. Use a min-heap. Frequent symbols get short codes, rare symbols get long codes. Proven optimal.

O(n log n)

O(n)

How It Works

Huffman coding builds a minimum-redundancy prefix code for compressing symbols with known frequencies. Put all symbols in a min-heap keyed by frequency, then repeatedly pop the two rarest nodes, merge them under a new internal node whose weight is their sum, and push it back. The final tree assigns each symbol a codeword given by its root-to-leaf path, so frequent symbols sit near the root with short codes and no codeword prefixes another.

Greedy is provably optimal here: some optimal tree always places the two least frequent symbols as deepest siblings, so merging them first never forecloses optimality, and induction finishes the proof. With n symbols the loop performs n-1 merges at O(log n) each — O(n log n) total. The same repeated cheapest-merge structure solves rope-joining cost problems directly.

Step-by-Step Visualization

Build Huffman tree from frequencies

CharsA:5, B:9, C:12, D:13, E:16, F:45

1/4

Code

Java

static int[] huffman(int[] freq) {
  PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
  for (int i = 0; i < freq.length; i++)
    pq.add(new int[]{freq[i], i});

  while (pq.size() > 1) {
    int[] left = pq.poll();
    int[] right = pq.poll();
    pq.add(new int[]{left[0] + right[0], -1});
  }
  return pq.poll(); // Root of Huffman tree
}

Tips & Gotchas

1Always merge the two nodes with smallest frequencies

2Use a min-heap to efficiently find minimum

3Resulting tree gives optimal prefix-free encoding

Practice Problems

1Minimum Cost to Connect Sticks
2Minimum Time to Build Blocks
3Last Stone Weight
4Reorganize String

About the Task Scheduling Pattern

Assign tasks to time slots or workers to maximize value or meet deadlines. Sort by a key metric (deadline, value, ratio), then greedily assign.

Key insight

Greedy is NOT 'try the obvious thing'. It works only when local optimality guarantees global optimality. Sort first (by end time, deadline, ratio), then pick greedily. If greedy fails, try DP.

Common Greedy Interview Problems

Jump Game
Activity Selection
Meeting Rooms II
Gas Station
Candy
Task Scheduler
Partition Labels

Frequently Asked Questions

What makes a prefix code decodable without separators?

No codeword is a prefix of another, because symbols live only at the leaves of the tree. A decoder walks from the root following each bit and emits a symbol whenever it lands on a leaf, restarting at the root — the boundaries are implicit in the tree structure.

Why do the two least frequent symbols merge first?

In any optimal tree, the deepest level contains at least two nodes, and swapping the rarest symbols into those deepest positions never increases total cost. That exchange argument means the greedy merge is always consistent with some optimal solution, which induction extends to full optimality.

Where else does the repeated cheapest-merge pattern show up?

Minimum Cost to Connect Sticks is Huffman's cost model verbatim: every merge of two sticks costs their sum, and total cost equals the weighted depth of the merge tree. Any problem where combining two items costs their combined weight and all items must merge into one fits the template.