Greedy Algorithms

The Greedy Strategy

An optimization problem asks for the best answer among many valid ones: the most meetings in one room, the fewest coins, the shortest encoding. A greedy algorithm builds the answer piece by piece. Each piece is chosen by a fixed rule and is never reconsidered.

The Usual Shape

Almost every greedy algorithm in this lesson follows the same pattern: sort by a key, then scan once and take each item that still fits.

sort items by KEY
for each item in that order {
	if item is compatible with what was already chosen {
		choose it // final: it is never removed later
	}
}

The cost is O(n log n) for the sort plus O(n) for the scan. Some greedy algorithms replace the sort with a heap because the best next choice changes as the algorithm runs, as in Dijkstra, Prim, and Huffman coding. Everything depends on the choice of KEY.

When Greedy Is Correct

A greedy algorithm is correct when the problem has two properties:

• Greedy-choice property: some optimal solution contains the first greedy choice. Taking it never rules out the best answer.
• Optimal substructure: after the choice, what remains is a smaller instance of the same problem, and an optimal answer to it combines with the choice into an optimal answer overall.

Optimal substructure is shared with dynamic programming, the next lesson. The difference is the first property. Dynamic programming tries every choice and keeps the best; greedy commits to one choice because it has proved that one is safe.

Proving It: the Exchange Argument

The standard proof technique works like this:

1. Take any optimal solution that differs from the greedy one.
2. Find the first place where they differ.
3. Show that replacing the optimal solution's choice there with the greedy choice keeps it valid and makes it no worse.
4. Repeat. The optimal solution turns into the greedy solution step by step without getting worse, so the greedy solution is optimal too.

A related technique, greedy stays ahead, shows that after every step the greedy partial answer is at least as good as any other partial answer of the same size. Both are used below.

Testing a Greedy Rule

A proof is the real guarantee, but a brute-force check is the fastest way to reject a wrong idea. Every demo in this lesson compares its greedy answer with an exhaustive search on thousands of small random inputs. A wrong rule usually fails within seconds. A rule that passes thousands of tests is worth trying to prove.

Interval Problems

Intervals are the classic training ground for greedy thinking, because several natural rules compete and only one of them works for each problem. Demo with four interval problems, each checked against brute force: 46_interval_scheduling.go.

Activity Selection

Given meetings with start and end times, schedule as many as possible in one room. Times are half-open, [start, end), so a meeting that ends at 4 does not clash with one that starts at 4. The correct rule is earliest end first: it leaves the most room for everything after it.

Scanning by end time: each taken meeting (green) ends as early as possible, so the next one can start as early as possible.

func maxActivities(iv []Interval) []Interval {
	sorted := slices.Clone(iv)
	slices.SortFunc(sorted, func(a, b Interval) int { return cmp.Compare(a.e, b.e) })
	var chosen []Interval
	lastEnd := -1 << 62
	for _, x := range sorted {
		if x.s >= lastEnd { // starts after (or exactly when) the last one ends
			chosen = append(chosen, x)
			lastEnd = x.e
		}
	}
	return chosen
}

Proof by exchange. Let f be the meeting that ends first. Take any optimal schedule and replace its first meeting with f. Since f ends no later, it cannot clash with anything the replaced meeting did not clash with. The schedule stays valid and has the same size, so some optimal schedule starts with f. The rest of the problem is the same problem on the meetings that start after f ends.

Three Wrong Rules

Each of these rules sounds reasonable. The demo shows a small input that defeats each one, and counts how often it fails on 3,000 random inputs:

Look at the third row. "Fewest clashes" is wrong only twice in 3,000 random tests, and its counterexample needs eleven carefully arranged meetings. A few hand-made examples would never find it. This is why a proof matters, and why random tests should run in the thousands.

Interval Partitioning

Now every meeting must happen: use the fewest rooms. Process meetings by start time, and keep a min-heap of the end times of the rooms in use. If the room that frees up first is free already, reuse it; otherwise open a new room.

for _, i := range order {
	if h.Len() > 0 && (*h)[0].end <= iv[i].s {
		r := heap.Pop(h).(roomEnd) // the earliest-free room is free now
		room[i] = r.room
	} else {
		room[i] = rooms // every room is busy: open a new one
		rooms++
	}
	heap.Push(h, roomEnd{iv[i].e, room[i]})
}

The proof uses a lower bound. If d meetings run at the same moment, no schedule can use fewer than d rooms. The greedy opens a new room only when every open room is busy at that start time, so it never opens more than d. Matching a lower bound is a second common way to prove a greedy algorithm optimal. The demo checks the room count against the maximum overlap and checks that no room hosts two overlapping meetings.

Merging and Stabbing Intervals

Two more problems follow the same pattern with a different key:

• Merge overlapping intervals: sort by start. Extend the current block while the next interval starts inside it; otherwise start a new block. The demo checks the result by painting every covered point on a grid.
• Fewest points that hit every interval (the "burst the balloons with arrows" puzzle): sort by end, and place a point at the end of the first interval that has not been hit. Any point further left would hit nothing more, and any point further right would miss this interval.

When Greedy Fails

The same greedy rule can be optimal for one family of inputs and wrong for a family that looks almost identical. Demo that measures both cases against exact answers: 47_when_greedy_fails.go.

Coin Change

To pay an amount with the fewest coins, a cashier takes as many of the largest coin as fit, then the next largest, and so on:

func greedyCoins(coins []int, amount int) int {
	n := 0
	for _, c := range coins {
		n += amount / c
		amount %= c
	}
	if amount != 0 {
		return -1 // stuck: greedy used coins that left an unpayable rest
	}
	return n
}

This is optimal for US and euro coins; the demo checks every amount up to 1,000. Change the coins and it breaks:

The exact answers come from a table of the best answer for every smaller amount. That table is dynamic programming, the subject of the next lesson.

Fractional vs 0/1 Knapsack

A bag holds 10 kg. Which items give the most value? The natural rule is best value per kilo first.

• If items can be cut (flour, fuel, bandwidth), this rule is optimal. Any kilo of a lower-value item can be exchanged for a kilo of a higher-value one without losing anything.
• If each item is taken whole or not at all (the 0/1 knapsack), the rule fails. In the demo, a camera (6 kg, 30) has the best value per kilo, but once it is in the bag the tent and the stove (5 kg, 20 each) no longer fit, and together they are worth 40. Greedy gets 35.

On 3,000 random 0/1 instances, "best value per kilo first" is wrong 638 times, "most valuable first" 481 times, and "lightest first" 1,811 times. The exchange argument breaks because whole items cannot be traded kilo for kilo. The 0/1 knapsack is solved exactly by dynamic programming in the next lesson.

Greedy as an Approximation

When no exact greedy exists, a greedy answer with a guarantee is often good enough. For the 0/1 knapsack, take the better of two answers: the density greedy, and the single most valuable item that fits. This is never below half the optimum. In the demo, the worst case over 3,000 random instances reached 63% of the optimum. Many hard problems in practice, such as scheduling, routing, and set cover, are handled with greedy algorithms whose worst case is proved.

Scheduling and the Exchange Argument

One machine runs jobs one after another, and the order decides the cost. These problems show the exchange argument at its clearest. Demo with every rule checked against all orderings: 48_scheduling_exchange.go.

Adjacent Swaps

For ordering problems, the exchange argument compares two adjacent jobs. Swapping two neighbours does not change when any other job starts or ends, so only the pair's own cost changes. If swapping every "wrongly ordered" neighbouring pair never makes the cost worse, then sorting by the rule is optimal, since bubble sort reaches the sorted order through exactly such swaps. The demo does this step by step, starting from a bad order:

  ABCD  cost 53
  BACD  cost 48   (swapped A and B)
  BCAD  cost 40   (swapped A and C)
  BCDA  cost 39   (swapped A and D)
Smith order cost: 39  best of all 24 orders: 39

Weighted Completion Time: Smith's Rule

Each job has a processing time t and a weight w (how much each unit of waiting costs). Minimize the sum of weight times finishing time. For two neighbours a then b, the swap changes the cost by a.t·b.w − b.t·a.w, so a should go first exactly when a.t / a.w ≤ b.t / b.w. Sort by that ratio, comparing by cross-multiplication to avoid floating point:

func smithCmp(a, b Job) int { return cmp.Compare(a.time*b.weight, b.time*a.weight) }

With all weights equal, this becomes shortest job first, which minimizes the total waiting time of a queue. That is why a supermarket express lane helps everyone's average wait.

Maximum Lateness: Earliest Deadline First

Each job has a due time, and the goal is to make the worst lateness as small as possible. Shortest job first is now wrong: in the demo it leaves the report 6 units late. Sorting by earliest deadline achieves the optimum of 1. In an adjacent pair, the second job finishes at the same moment whichever job goes second, so the job with the later deadline should take that slot.

Among 1,000 random job sets, each rule matched the best of all orderings for its own objective in every case. Used for the other objective, shortest job first was wrong 730 times for weighted completion and 734 times for lateness. A greedy rule is tied to one objective.

Unit Jobs with Deadlines and Profits

Every job takes one time slot and pays its profit only if it finishes by its deadline. Take jobs from the most profitable down. Put each one in the latest free slot on or before its deadline, which keeps earlier slots open for jobs with tighter deadlines, and skip it if no slot is free. Searching backwards for a free slot costs O(n) per job. Union-find from Graph Traversal makes it nearly O(1): each slot points to the latest free slot at or before it, and a used slot is linked to the one before it.

slot = make([]int, len(offers)) // 0 = not scheduled
for _, i := range order {
	s := find(offers[i].due) // latest free slot on or before the deadline
	if s > 0 {
		slot[i] = s
		profit += offers[i].profit
		parent[s] = s - 1 // slot s is taken: next time look further left
	}
}

The demo checks the profit against every subset of jobs. A subset can be scheduled exactly when, sorted by deadline, its k-th job has a deadline of at least k.

Huffman Coding

Huffman coding is a greedy algorithm that builds a tree instead of choosing items. It is part of the DEFLATE format used by zip, gzip, and PNG, and of JPEG. Demo that builds the code, encodes and decodes a text, and checks optimality: 49_huffman.go.

Prefix-Free Codes

Give each symbol a binary code so that frequent symbols get short codes. The codes must be prefix-free: no code may be the start of another. Otherwise decoding is ambiguous. With a = 0 and b = 01, the bits 01 could be b, or a followed by something else. A prefix-free code is exactly a binary tree with the symbols at the leaves: the path from the root spells the code, with 0 for left and 1 for right. Decoding walks down from the root and restarts there at every leaf.

"abracadabra" in 23 bits instead of 33 with a fixed 3-bit code. The most frequent symbol has a 1-bit code.

Building the Tree

The greedy rule: repeatedly merge the two least frequent trees into one whose weight is their sum. A min-heap from Heaps gives each merge in O(log n), so the whole tree takes O(n log n) for n distinct symbols.

func buildTree(freq map[rune]int) *Node {
	h := &nodeHeap{}
	for s, f := range freq {
		*h = append(*h, &Node{weight: f, sym: s, minSym: s})
	}
	heap.Init(h) // O(n) bottom-up build (see Heaps, Phase 2)
	if h.Len() == 1 {
		// One distinct symbol: give it a parent so its code is "0", not "".
		only := heap.Pop(h).(*Node)
		return &Node{weight: only.weight, left: only, minSym: only.sym}
	}
	for h.Len() > 1 {
		a := heap.Pop(h).(*Node) // the two least frequent trees
		b := heap.Pop(h).(*Node)
		heap.Push(h, &Node{weight: a.weight + b.weight, left: a, right: b, minSym: min(a.minSym, b.minSym)})
	}
	return heap.Pop(h).(*Node)
}

The minSym field breaks ties between equal weights, so the demo prints the same codes on every run. Without it, codes depend on Go's random map iteration order. They would still be optimal, but they would differ from run to run.

Why It Is Optimal

In some optimal tree, the two rarest symbols are siblings at the deepest level. If a rarer symbol sat higher than a more frequent one, swapping them would not increase the total length. So merging the two rarest symbols first is safe. After the merge, they behave like one symbol whose weight is their sum, which is the same problem with one fewer symbol.

The demo's oracle does not use this idea at all. Kraft's inequality says code lengths l₁, …, lₙ can be realised by a prefix-free code exactly when the sum of 2^−lᵢ is at most 1. The oracle tries every such set of lengths for alphabets of up to 7 symbols, and Huffman matches the minimum in all 1,500 tests. For comparison, the older top-down method (Shannon-Fano coding, which splits the symbols into two halves of nearly equal weight) is prefix-free but longer than optimal in 43 of 1,500 tests.

Common Pitfalls

Greedy bugs rarely crash. They return a valid answer that is slightly worse than the best one, which is easy to miss.

Trusting an Unproven Rule

A rule that works on every example you tried can still be wrong, as the "fewest clashes" rule shows. Before you ship a greedy algorithm, either write down the exchange argument or compare it with brute force on thousands of small random inputs.

Sorting by the Wrong Key or Comparing Ratios Badly

Start time or end time, value or value per kilo: the key is the algorithm. When the key is a ratio, compare a.t*b.w with b.t*a.w instead of dividing. Floating-point ratios can make equal ratios compare as different, and integer division rounds them. Watch for overflow in the products, as with the a - b comparator bug in Sorting.

Open and Closed Endpoints

Decide whether touching intervals overlap before writing the comparison. Meetings [1, 4) and [4, 6) are compatible, and the test is x.s >= lastEnd. Closed intervals [1, 4] and [4, 6] share the point 4, so the test becomes x.s > lastEnd. A wrong > versus >= passes most tests and fails at the boundary.

Practice Lab

For each exercise, state your greedy rule first, then try to break it with a small counterexample before you write code.

Run the Demos

1. In 46_interval_scheduling.go, sort by start time instead of end time in maxActivities. How many random inputs now disagree with brute force?
2. In 47_when_greedy_fails.go, add a 20-cent coin to the US system. What is the first amount the cashier's rule now gets wrong?
3. In 48_scheduling_exchange.go, sort the offers in maxProfit by deadline instead of profit. Why does the check fail?
4. In 49_huffman.go, make Less prefer the heavier tree. The codes stay prefix-free and the round trip still works. What fails, and why?

Exercises

1. Jump game. Each array cell says how far you may jump forward from it. Decide whether the last cell is reachable, in one pass, by tracking the farthest reachable index.
2. Gas station. Stations on a circular road give fuel and cost fuel to reach the next one. Find the starting station for a full lap in O(n). Prove that if the tank goes negative after station i, no station from the start up to i can be the answer.
3. Minimum platforms. Given train arrival and departure times, find how many platforms a station needs. Solve it with the room heap, then with two sorted arrays and two pointers.
4. Break the rule. For "fewest clashes first" in activity selection, write a program that searches random inputs for the smallest counterexample. How many intervals does it need?

Continue with Dynamic Programming, which solves the problems where greedy fails.