Greedy PrinciplesWhen greedy is correct

01Why it exists

Reach for it when you see:Take the largest / smallest / earliest at every step, sort then scan once, never look back, locally optimal, exchange argument, counterexample.

02The core idea

The shape of a greedy algorithm never varies: sort the candidates by some rule, look at them one at a time, take whatever fits, and never revisit a decision. It never backtracks and never compares alternative selections, so it usually costs no more than O(n log n) for the sort plus O(n) for the scan. The price of that speed is that it is not always right, and whether a particular greedy rule is right depends on whether the problem has two properties.

The first is the greedy choice property: some optimal solution starts with the same move greedy makes. The second is optimal substructure: what remains after that first move is a problem of the same shape but smaller, and its optimal solution, with the first move attached, is optimal for the original problem. When both hold, every greedy step keeps the partial answer consistent with some optimal solution, so running all the way to the end produces one.

The standard tool for proving the greedy choice property is the exchange argument. Take any optimal solution O and find the first place where it differs from the greedy solution G; replace O's choice there with G's, and argue that O is still valid afterwards and no worse than before. That shows an optimal solution consistent with greedy exists. In interval scheduling, greedy takes the earliest-finishing interval G₁, and the first interval to finish in any optimal solution, O₁, cannot finish before G₁ does, so swapping O₁ for G₁ still leaves room for everything after it. Going the other way, both "earliest start" and "shortest" have counterexamples: an exchange there may have to give back two intervals or more, and the argument cannot be completed.

In practice the order of work is: guess a rule, hunt for a counterexample on small inputs (by hand, or against a brute-force solution), and switch rules or switch to DP the moment you find one; only when nothing turns up do you attempt the exchange argument. A common trap is treating "it passed a few test cases" as a proof, since a greedy rule usually fails only on particular inputs — [1, 3, 4] in the making-change problem is the classic example. Another is thinking of greedy and DP as opposites: greedy is really a special case of DP, and when the best transition out of every state can be decided without looking at the alternatives, DP degenerates into greedy.

03The algorithm

1. 1Write the problem as a sequence of choices, where each choice leaves behind a smaller problem of the same shape.
2. 2Guess a sort key (earliest finish, smallest, best ratio, …), sort by it, scan through, and take whatever fits.
3. 3Hunt for a counterexample on small inputs: work 5 to 10 elements through by hand, or write a brute-force solution and compare on n ≤ 15. One counterexample means a different key, or no greedy at all.
4. 4If nothing turns up, build an exchange argument: take any optimal solution O, replace its first choice that differs from the greedy one with the greedy choice, and argue that the result is still valid and no worse.
5. 5Confirm the optimal substructure: after the first choice, what is left has the same shape. With both properties in hand the greedy answer is optimal, and the cost is usually O(n log n).

04Interactive demo

The same seven intervals under three greedy rules, stepping through what each rule takes and what it skips. The optimum is four. The panel at the bottom right explains why the rule works or why it fails: the correct one gets an exchange argument, and each wrong one gets a concrete counterexample.

05Code

A generic sort-then-scan skeleton with three interchangeable sort keys, plus a brute-force solution to check against. This is exactly how you hunt for counterexamples: run greedy and brute force side by side on small inputs. So that all three rules can share it, the skeleton compares every candidate against all the intervals chosen so far; once you have committed to sorting by finish time, comparing against the last chosen one is enough, and the Interval Scheduling lesson writes it that way in O(n log n).

# Interval scheduling: one skeleton, three sort keys, and only "earliest finish" is correct
def schedule(intervals, key):
    """intervals is a list of (start, end); key decides the greedy order.
    Returns the chosen intervals, none of which overlap (touching endpoints are allowed)."""
    chosen = []
    for s, e in sorted(intervals, key=key):
        # Only take an interval that clashes with none of the chosen ones. Comparing against the
        # last finish time alone is not enough: sorting by length can hand us an earlier interval later
        if all(e <= cs or s >= ce for cs, ce in chosen):
            chosen.append((s, e))
    return chosen


def by_start(iv):                             # earliest start: wrong
    return iv[0]

def by_length(iv):                            # shortest: wrong
    return (iv[1] - iv[0], iv[0])

def by_end(iv):                               # earliest finish: correct
    return iv[1]


# Brute force: enumerate every subset on small inputs and see whether greedy reached the optimum
# Run this first when no exchange argument comes to mind; a counterexample saves you the proof
from itertools import combinations

def brute_force(intervals):
    n = len(intervals)
    for r in range(n, 0, -1):                 # largest sizes first, so the first feasible one is optimal
        for subset in combinations(intervals, r):
            ok = all(a[1] <= b[0] or b[1] <= a[0] for a, b in combinations(subset, 2))
            if ok:
                return r
    return 0


if __name__ == "__main__":
    ivs = [(0, 12), (1, 5), (4, 7), (6, 10), (11, 14), (13, 16), (15, 18)]
    print(brute_force(ivs))                   # 4
    for name, key in [("start", by_start), ("length", by_length), ("end", by_end)]:
        print(name, len(schedule(ivs, key)))  # start 2, length 3, end 4

06Practice

• LeetCode 455Assign Cookies (sort, then two pointers)Easy
• LeetCode 1029Two City Scheduling (sort by the difference)Medium
• LeetCode 763Partition LabelsMedium
• LeetCode 406Queue Reconstruction by HeightMedium
• LeetCode 621Task SchedulerMedium
• LeetCode 135Candy (two greedy passes)Hard