Greedy Algorithms

Greedy: commit locally, never reconsider

A greedy algorithm builds a solution one piece at a time, always taking the choice that looks best right now and never undoing it. No backtracking, no table of subproblems — just a single forward pass, which is why greedy is typically the fastest approach when it works.

But “when it works” is the whole catch. Greedy is correct only when the problem has two properties:

• Greedy-choice property — a globally optimal solution can be reached by a sequence of locally optimal choices. The best first move is safe to lock in.
• Optimal substructure — after making that choice, what remains is a smaller instance of the same problem, and an optimal solution to it extends your choice into a global optimum.

When those hold, greedy is provably optimal and fast. When they don’t, you need dynamic programming, which explores all options instead of committing early.

graph TD
S["problem"] --> C{"greedy-choice<br/>property?"}
C -->|yes| G["greedy: one pass, locally optimal"]
C -->|no| D["dynamic programming: explore all options"]
classDef good fill:#0f2a1a,stroke:#22c55e,color:#d7ffe9;
classDef warn fill:#2a0f17,stroke:#f43f5e,color:#ffd7e0;
class G good;
class D warn;

A few classics greedy nails: interval scheduling (most non-overlapping meetings → sort by earliest finish), coin change for canonical systems (US coins → always grab the largest that fits), and Huffman coding (repeatedly merge the two least-frequent symbols to build an optimal prefix code).

Interval scheduling by earliest finish time

You have a set of meetings, each with a start and finish time, and one room. Pick the most meetings that don’t overlap. The optimal greedy rule is counterintuitive: ignore start times and sort by finish time, then walk through taking any meeting that starts at or after the last one you took finishes. Finishing early leaves the most room for what follows.

package main

import (
"fmt"
"sort"
)

type Interval struct {
name       string
start, fin int
}

// maxNonOverlapping returns the largest set of mutually non-overlapping intervals.
// Greedy: sort by finish time, then take each that starts at/after the last finish.
func maxNonOverlapping(items []Interval) []Interval {
sort.Slice(items, func(i, j int) bool {
	if items[i].fin != items[j].fin {
		return items[i].fin < items[j].fin
	}
	return items[i].start < items[j].start // tie-break for deterministic output
})

var chosen []Interval
lastFinish := -1 << 30
for _, it := range items {
	if it.start >= lastFinish {
		chosen = append(chosen, it)
		lastFinish = it.fin
	}
}
return chosen
}

func main() {
meetings := []Interval{
	{"A", 1, 4},
	{"B", 3, 5},
	{"C", 0, 6},
	{"D", 5, 7},
	{"E", 3, 9},
	{"F", 8, 9},
}

chosen := maxNonOverlapping(meetings)
fmt.Printf("picked %d non-overlapping meetings:\n", len(chosen))
for _, it := range chosen {
	fmt.Printf("  %s [%d, %d)\n", it.name, it.start, it.fin)
}
}

The greedy pass picks A, D, F — three meetings — and no other selection does better. Crucially, picking the longest meeting C [0,6) first would have blocked everything else; earliest-finish avoids that trap.

Where greedy fails: coin change

The same “take the biggest that fits” instinct that works for US coins breaks on other systems. With coins [1, 3, 4] and amount 6, greedy grabs 4, then is forced into 1 + 1 — 3 coins. The real optimum is 3 + 3 — 2 coins — which requires not taking the largest coin. Greedy can’t see that because it never reconsiders.

This playground runs both and prints the gap, so the failure is concrete and deterministic:

package main

import (
"fmt"
"sort"
)

// greedyCoins: take the largest coin that fits, repeatedly. Fast but not always optimal.
func greedyCoins(coins []int, amount int) int {
sorted := append([]int(nil), coins...)
sort.Sort(sort.Reverse(sort.IntSlice(sorted))) // largest first, deterministic
count := 0
for _, c := range sorted {
	for amount >= c {
		amount -= c
		count++
	}
}
if amount != 0 {
	return -1 // greedy got stuck
}
return count
}

// dpCoins: bottom-up DP, always the true minimum.
func dpCoins(coins []int, amount int) int {
const unreachable = 1 << 30
dp := make([]int, amount+1)
for a := 1; a <= amount; a++ {
	dp[a] = unreachable
	for _, c := range coins {
		if c <= a && dp[a-c]+1 < dp[a] {
			dp[a] = dp[a-c] + 1
		}
	}
}
if dp[amount] >= unreachable {
	return -1
}
return dp[amount]
}

func main() {
coins := []int{1, 3, 4}
amount := 6

g := greedyCoins(coins, amount)
d := dpCoins(coins, amount)

fmt.Printf("coins %v, amount %d\n", coins, amount)
fmt.Printf("greedy: %d coins (4+1+1)\n", g)
fmt.Printf("DP:     %d coins (3+3, optimal)\n", d)
fmt.Printf("greedy is wrong by %d coin(s)\n", g-d)
}

See also

• dynamic programming — the fallback when local choices aren’t globally safe.
• union-find — the engine of Kruskal’s greedy MST.
• graphs — Dijkstra and Prim are greedy graph algorithms.
• sorting — most greedy algorithms start by sorting.

Next: the whole track on one page — the DSA cheat-sheet.

Related topics