Greedy Algorithm Pattern
What Is a Greedy Algorithm?
A greedy algorithm builds a solution one step at a time, always taking the option that looks best right now, and never reconsidering that choice.
GREEDY: make the locally best choice → commit → repeat BACKTRACKING: try a choice → explore → undo if needed → try the next DYNAMIC PROGRAMMING: consider ALL choices → remember the best result per state Greedy is the fastest of the three (often O(n log n) for a sort + O(n) scan), but it is only CORRECT when the problem has the greedy-choice property: "some optimal solution begins with the greedy choice."
The hard part of greedy is never the code — it is knowing that the greedy choice is safe.
Example 1: Most Non-Overlapping Bookings
A room has booking requests as [start, end) time ranges. Accept as many as possible with no two overlapping.
requests: [9,12) [1,3) [2,5) [4,7) [6,8) [8,10) [11,13) [3,4) Candidate rules: earliest START first? can pick a long booking that blocks many short ones ✗ SHORTEST first? a short booking can straddle two compatible ones ✗ earliest END first? ✓ — leaves the most time for the rest sorted by end: [1,3) [3,4) [2,5) [4,7) [6,8) [8,10) [9,12) [11,13) [1,3) nothing kept → keep free_at = 3 [3,4) 3 ≥ 3 → keep free_at = 4 [2,5) 2 < 4 → skip (overlaps) [4,7) 4 ≥ 4 → keep free_at = 7 [6,8) 6 < 7 → skip [8,10) 8 ≥ 7 → keep free_at = 10 [9,12) 9 < 10 → skip [11,13) 11 ≥ 10 → keep Kept 5: [1,3) [3,4) [4,7) [8,10) [11,13)
Why It's Correct (Exchange Argument)
Let OPT be any best schedule, and g the booking that ends earliest overall.
Let o be the first booking in OPT.
g ends no later than o (g ends earliest of all).
So replacing o by g cannot create an overlap with OPT's later bookings.
→ OPT' = OPT − {o} + {g} is still valid and has the same size.
So SOME optimal schedule starts with g. Remove everything overlapping g
and repeat the same argument on what's left. Greedy is optimal.
Example 2: Hopping to the Last Stone
Each stone i lets you hop forward up to hops[i] stones. Starting on stone 0, can you reach the last one?
hops = [3, 1, 0, 2, 0, 1] i=0: farthest = max(0, 0+3) = 3 i=1: farthest = max(3, 1+1) = 3 i=2: farthest = max(3, 2+0) = 3 i=3: farthest = max(3, 3+2) = 5 ← last index reached ✓ hops = [2, 1, 0, 3] i=0: farthest 2; i=1: 2; i=2: 2 i=3: 3 > farthest (2) → stone 3 is unreachable ✗
The greedy insight: the set of reachable stones is always a prefix 0 … farthest, so one number captures everything.
Example 3: Filling a Bag With Divisible Goods
Spices can be taken in any amount. Each has a total weight and total value. Fill a bag of capacity 15 to maximise value.
spice weight value value/weight A 4 40 10.0 B 10 30 3.0 C 6 24 4.0 D 20 10 0.5 Take by density: A (all 4 → 40), C (all 6 → 24), B (5 of 10 → 15) capacity used 15, value = 79.00
Because goods are divisible, the bag is always filled exactly with the densest material available — no better mix exists.
Example 4: When Greedy Fails
COINS [1, 5, 10, 25], amount 63: greedy: 25 + 25 + 10 + 1 + 1 + 1 = 6 coins optimal: 6 ✓ COINS [1, 3, 4], amount 6: greedy: 4 + 1 + 1 = 3 coins optimal: 3 + 3 = 2 ✗ Greedy's first choice (4) is not part of any optimal answer. No exchange argument exists → use dynamic programming instead.
Code: Three Correct Greedies and One That Fails
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class GreedyPattern {
// 1. Most non-overlapping bookings — keep the one that ENDS first
static List<int[]> maxBookings(int[][] bookings) {
int[][] sorted = bookings.clone();
Arrays.sort(sorted, (a, b) -> Integer.compare(a[1], b[1]));
List<int[]> chosen = new ArrayList<>();
int freeAt = Integer.MIN_VALUE;
for (int[] b : sorted) {
if (b[0] >= freeAt) { chosen.add(b); freeAt = b[1]; } // compatible → keep
}
return chosen;
}
// 2. Can we hop to the last stone? Track the farthest reachable index
static boolean canReachEnd(int[] hops) {
int farthest = 0;
for (int i = 0; i < hops.length; i++) {
if (i > farthest) return false; // this stone is unreachable
farthest = Math.max(farthest, i + hops[i]);
}
return true;
}
// 3. Divisible goods into a bag — best value per unit first
static double bestBagValue(int[][] items, int capacity) {
int[][] sorted = items.clone();
Arrays.sort(sorted, (a, b) -> Double.compare((double) b[1] / b[0], (double) a[1] / a[0]));
double total = 0;
for (int[] it : sorted) {
int take = Math.min(it[0], capacity);
total += (double) it[1] * take / it[0];
capacity -= take;
if (capacity == 0) break;
}
return total;
}
// 4. Greedy coin change vs the true optimum (DP)
static int greedyCoins(int[] coins, int amount) {
int[] c = coins.clone();
Arrays.sort(c);
int count = 0;
for (int i = c.length - 1; i >= 0; i--) { count += amount / c[i]; amount %= c[i]; }
return amount == 0 ? count : -1;
}
static int optimalCoins(int[] coins, int amount) {
int INF = amount + 1;
int[] best = new int[amount + 1];
Arrays.fill(best, INF);
best[0] = 0;
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;
return best[amount] < INF ? best[amount] : -1;
}
public static void main(String[] args) {
int[][] bookings = {{9, 12}, {1, 3}, {2, 5}, {4, 7}, {6, 8}, {8, 10}, {11, 13}, {3, 4}};
List<int[]> kept = maxBookings(bookings);
StringBuilder sb = new StringBuilder("bookings kept (" + kept.size() + "):");
for (int[] b : kept) sb.append(" [").append(b[0]).append(",").append(b[1]).append(")");
System.out.println(sb);
for (int[] hops : new int[][]{{3, 1, 0, 2, 0, 1}, {2, 1, 0, 3}})
System.out.println("reach end with " + Arrays.toString(hops) + ": " + canReachEnd(hops));
int[][] spices = {{4, 40}, {10, 30}, {6, 24}, {20, 10}};
System.out.println(String.format("best bag value (capacity 15): %.2f", bestBagValue(spices, 15)));
int[][] coinSets = {{1, 5, 10, 25}, {1, 3, 4}};
int[] amounts = {63, 6};
for (int k = 0; k < 2; k++)
System.out.println("coins " + Arrays.toString(coinSets[k]) + " for " + amounts[k]
+ ": greedy " + greedyCoins(coinSets[k], amounts[k])
+ ", optimal " + optimalCoins(coinSets[k], amounts[k]));
}
}Output:
bookings kept (5): [1,3) [3,4) [4,7) [8,10) [11,13)
reach end with [3, 1, 0, 2, 0, 1]: true
reach end with [2, 1, 0, 3]: false
best bag value (capacity 15): 79.00
coins [1, 5, 10, 25] for 63: greedy 6, optimal 6
coins [1, 3, 4] for 6: greedy 3, optimal 2
How to Tell If Greedy Will Work
1. STATE THE GREEDY RULE in one sentence. "Always take the booking that ends first." 2. HUNT FOR A COUNTER-EXAMPLE with 2–4 items. Try the cases that break naive rules: one long item vs two short, ties, an item that is best now but blocks two good ones later. Found one? → greedy fails; consider DP. 3. TRY AN EXCHANGE ARGUMENT. Take any optimal answer. Swap its first choice for the greedy choice. Is it still valid and no worse? → greedy is safe. 4. OR A "STAYS AHEAD" ARGUMENT. After k steps, greedy's partial answer is at least as good as any other algorithm's after k steps (e.g. greedy's k-th booking ends no later than OPT's k-th booking).
Common Greedy Rules
| Problem shape | Sort / choose by | Why it works |
|---|---|---|
| Max non-overlapping intervals | earliest end | leaves the most room |
| Min points to hit every interval | earliest end, place point at the end | one point covers all overlapping |
| Reachability / min hops | farthest reach so far | reachable set is a prefix |
| Divisible packing | value / weight, descending | the bag fills exactly with the densest |
| Pair small with large (e.g. boats of 2) | sort, two pointers | heaviest must pair with lightest if anyone |
| Task deadlines, unit time | process by deadline, drop the largest so far when late | exchange argument |
| Merge cheapest first (e.g. joining ropes) | min-heap of sizes | cheaper merges should happen deeper |
Many greedy algorithms are "sort + one pass" or "heap + one pass" — see the Heap Pattern for the second kind.
Greedy vs Dynamic Programming
GREEDY DP
Choices kept one per step all, summarised per state
Revisits choices never implicitly (compares options)
Typical time O(n log n) O(n · W), O(n²), ...
Correctness needs a proof follows from the recurrence
Fails when an early best choice — (always correct if the
blocks a better total state is right)
Divisible packing → greedy | 0/1 packing → DP
Max # intervals → greedy | max WEIGHTED intervals → DP
Canonical coins → greedy | arbitrary coins → DP
See Dynamic Programming Basics for the DP side.
Common Mistakes
Picking the intuitive rule without testing it. "Shortest first" and "earliest start first" feel right for scheduling and both fail.
Using greedy for 0/1 choices. Value density is optimal only when items can be split.
Forgetting ties. Two items with the same sort key may need a secondary rule (e.g. same end time → either is fine; same density → either is fine; but some problems need a specific tie-break).
Overlap definition off by one. [1,3) and [3,4) don't overlap with half-open intervals; with closed intervals [1,3] and [3,4] they do. Match >= vs > to the problem.
Interview Questions
Q: Prove that earliest-end-first maximises the number of non-overlapping intervals.
Let g be the interval with the earliest end. In any optimal schedule, replace its first interval with g. Since g ends no later, it overlaps nothing that the original first interval didn't, so the new schedule is valid and the same size. Thus some optimal schedule contains g. Remove intervals overlapping g and apply the same argument to the remainder — by induction greedy is optimal.
Q: How do you quickly check whether greedy coin change is safe for a given coin set?
Compare greedy against DP for every amount up to the sum of the two largest coins. If they agree on all of them, the system is canonical and greedy is safe for every amount. For interviews, a single counter-example (like [1, 3, 4] with 6) is enough to reject greedy.
Q: Why is weighted interval scheduling not greedy?
Weights break the exchange argument: replacing the first chosen interval with the earliest-ending one keeps the count but can lower the total weight. You need DP over intervals sorted by end time, with a binary search for the last compatible interval.
Summary
- ›Greedy takes the locally best choice and never looks back — fast, but only correct with the greedy-choice property.
- ›Prove it with an exchange or stays-ahead argument; disprove it with a tiny counter-example.
- ›Classic safe rules: earliest end, farthest reach, best density for divisible goods.
- ›Classic failures: arbitrary coins, 0/1 packing, weighted intervals → use DP.
Next, Divide & Conquer splits a problem into independent halves, solves each recursively, and combines the answers — the idea behind merge sort, fast exponentiation, and counting inversions.
To keep the MOST non-overlapping bookings, which booking should be taken first?