GreedyAlgorithmaka greedy paradigm, greedy choice

Greedy Algorithms

Build a solution by repeatedly taking the locally best choice — correct only when an exchange argument proves that choice never hurts.

Pattern: Greedy Practice (9)

Progress

Overview

A greedy algorithm makes one irrevocable decision at a time using a simple rule ("earliest finishing interval", "cheapest edge", "highest value per weight") and never reconsiders it. When it works it is usually the fastest possible approach — typically a sort followed by a single sweep, O(n log n).

The catch is that greedy is a proof obligation, not a technique: the same local rule that solves Activity Selection optimally gives wrong answers for weighted intervals or 0/1 Knapsack. Before trusting a greedy solution you must argue that a locally best choice can always be extended to a globally optimal one.

paradigmexchange argumentmatroidsort then sweep

Intuition

A mental model before the formal terms.

Imagine paying 63 cents with coins 25, 10, 5, 1: take the biggest coin that fits, repeat. It works because every coin is a multiple of the next smaller one, so a larger coin can always replace a group of smaller ones without loss. With coins {1, 3, 4} and amount 6 the same rule takes 4 + 1 + 1 (three coins) while 3 + 3 (two coins) is optimal — the structure that made greedy safe is gone.

How it works

Identify the greedy choice: a rule that picks one element using only local information (usually after sorting by some key).
Show the greedy-choice property: some optimal solution contains that first choice. The standard tool is an exchange argument — take any optimal solution, swap in the greedy choice, and show nothing gets worse.
Show optimal substructure: after the choice, what remains is a smaller instance of the same problem, so induction finishes the proof.
Implement as sort + sweep, or with a Priority Queue when the "best remaining" element changes dynamically (Huffman, Dijkstra, Prim).

Why it works

The exchange argument is the whole story. For activity selection: let g be the interval that finishes earliest and o the first interval in some optimal schedule. Since g finishes no later than o, replacing o with g keeps the schedule feasible and the same size — so an optimal schedule starting with g exists, and the remaining problem is the same problem on intervals starting after g ends.

Formally, problems where greedy is always optimal are exactly the matroids (and their generalizations); MST is the canonical example. You do not need the theory in interviews, but you do need a concrete exchange argument for your specific rule.

Recognition

How to tell a problem wants this.

The statement asks for a maximum count or minimum cost with a natural ordering key (finish time, deadline, ratio, weight).
Choices do not interact except through a simple resource (time, capacity, one machine): "schedule as many as possible", "minimum number of intervals to remove", "can you reach the end".
A small example where taking the obvious best choice first is provably fine — and no counterexample after trying to break it.
Constraints of n ≤ 10^5 with a single sort suggesting O(n log n).

“maximum number of non-overlapping” → Greedy “overlapping intervals” → Intervals

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1sort items by the greedy key
2solution = []
3for item in items:
4  if item is compatible with solution:
5    solution.add(item)   # never undone
6return solution

Implementations

1import math
2 
3# Greedy: build the answer by repeatedly taking the locally best option.
4# This is only correct when an EXCHANGE ARGUMENT holds — that swapping any
5# optimal solution toward the greedy choice never makes it worse. The two
6# functions below are the same shape; only one of them is correct.
7 
8 
91 · Correct greedy: coin change with a canonical system (1, 5, 10, 25)
10def coins_canonical(amount: int, coins: list[int]) -> int:
11    count = 0
12    rest = amount
13    for c in coins:  # coins sorted descending
14        q, rest = divmod(rest, c)
15        count += q
16    return count if rest == 0 else -1
17 
18 
192 · The same greedy is WRONG for a non-canonical system like {1, 3, 4}:
20# greedy gives 6 = 4+1+1 (3 coins), the optimum is 3+3 (2 coins)
21def coins_dp(amount: int, coins: list[int]) -> int:
22    dp = [math.inf] * (amount + 1)
23    dp[0] = 0
24    for a in range(1, amount + 1):
25        for c in coins:
26            if c <= a and dp[a - c] + 1 < dp[a]:
27                dp[a] = dp[a - c] + 1
28    return -1 if dp[amount] == math.inf else int(dp[amount])
29 
30 
313 · A greedy that IS provable: to cover points with unit intervals, always
32# place the interval starting at the leftmost uncovered point
33def min_unit_intervals(points: list[int], width: int) -> int:
34    ordered = sorted(points)
35    used = 0
36    i = 0
37    while i < len(ordered):
38        used += 1
39        end = ordered[i] + width  # the interval [ordered[i], ordered[i]+width]
40        while i < len(ordered) and ordered[i] <= end:
41            i += 1
42    return used
43 
44 
454 · The exchange argument for it: any optimal cover can be rewritten to
46# start its leftmost interval at the leftmost uncovered point without using
47# more intervals, because that placement covers a superset of what any
48# interval covering that point could cover to its right.
49 
50 
515 · The practical test: sort by some key, take greedily, and CHECK against
52# brute force on small inputs before trusting it
53def greedy_matches_optimal(amount: int, coins_desc: list[int]) -> bool:
54    return all(coins_canonical(a, coins_desc) == coins_dp(a, coins_desc) for a in range(amount + 1))

Walkthrough

divmod(rest, c) returns quotient and remainder in one call, which is both faster and clearer than computing them separately.
sorted(points) returns a new list, so the function is side-effect free by default — the opposite of list.sort().
math.inf as the DP sentinel needs no overflow guard; the explicit dp[a - c] + 1 < dp[a] comparison also avoids a min() call per candidate.
The all(... for a in range(...)) generator in greedy_matches_optimal short-circuits on the first mismatch.
int(dp[amount]) converts back from the float math.inf domain, which is the small cost of using math.inf in an integer table.

Complexity (this implementation)

time O(k) greedy, O(amount * k) DP, O(n log n) interval cover · space O(1), O(amount), O(n)

Language notes

divmod(a, b) is a single call returning both results and is the idiomatic spelling for this pattern.
sorted() copies while list.sort() mutates — choosing the former is what makes min_unit_intervals free of side effects.
math.inf is a float, so an integer DP table becomes float-typed; a large integer sentinel keeps it list[int].
hypothesis is the natural tool for the verify-against-brute-force habit this entry advocates, generating small random inputs automatically.

Common mistakes in this language

Using list.sort() and mutating the caller's list when sorted() was intended.
Trusting a greedy without the cross-check, which is the entire point of the entry.
Leaving math.inf in a table that downstream code expects to be integers.

Language differences that matter here

JavaScript is the only language whose default sort actively breaks greedy algorithms: without a comparator it orders numbers lexicographically, so a "sort then take greedily" solution silently takes the wrong things.
Integer division: Python divmod gives both results in one call, C++ / and % on ints already truncate, and JS/TS need Math.floor around a float division.
Sentinels: Infinity and math.inf saturate safely; C++ INT_MAX requires an explicit reachability guard before any addition.
Sorting side effects: Python sorted() copies by default and list.sort() mutates; C++ std::sort and JS/TS sort always mutate, so a copy must be made deliberately.

Complexity

Best

O(n)

Average

O(n log n)

Worst

O(n log n)

Space

O(1)

Dominated by the sort; O(n log n) with a heap when the best remaining choice changes dynamically.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

You can state and defend an exchange argument for the greedy choice.
Interval scheduling, interval partitioning, deadline scheduling, Huffman coding, MST, Dijkstra, fractional knapsack, jump game, gas station.
The DP formulation exists but the optimal transition is always the same "obvious" one — then greedy is the DP with the search removed.

Avoid it when

0/1 knapsack: items (weight, value) = (10, 60), (20, 100), (30, 120) with capacity 50 — greedy by ratio takes 160, optimal is 220.
Coin change with arbitrary denominations ({1, 3, 4}, amount 6).
Weighted interval scheduling, longest path, or any problem where an early choice constrains later ones in a non-local way — use Dynamic Programming.
When you cannot find the exchange argument. A greedy that "seems to work on examples" is the most common wrong answer in interviews.

Alternatives

Dynamic Programming Divide and Conquer Subsets (Power Set)

Common mistakes

Choosing the wrong greedy key (sorting intervals by start time instead of finish time).
Skipping the proof and shipping a greedy that fails on a hidden case.
Confusing greedy with DP: DP explores all transitions and keeps the best; greedy commits to one.
Forgetting ties: several keys equal — pick the tie-break that keeps the exchange argument valid.

Interview patterns

Sort by finish time, sweep, count compatible intervals.
Sort by deadline / by ratio, then use a heap to undo the worst earlier choice (job sequencing, "IPO", "maximum performance of a team").
Farthest-reach greedy: jump game, minimum jumps, video stitching.
Two-phase "prove greedy then implement": state the exchange argument aloud before coding.

Interview questions on this

Greedy or dynamic programming?Advanced
Convincing me your algorithm is correctExpert

Mock interviews

Merge IntervalsIntermediate

Example problems

Task Schedulermedium Meeting Rooms IImedium Non-overlapping Intervalsmedium Gas Stationmedium Jump Gamemedium Activity Selectioneasy Fractional Knapsackeasy Job Sequencing with Deadlinesmedium Huffman Codingmedium