Greedy: when the local choice is the global one

Every technique this site has taught you so far makes you inspect the whole problem before moving: sorting reorganizes everything, dynamic programming keeps every branch it could have taken alive, and graphs search until they find the answer. Greedy algorithms do the opposite. At each step, choose what looks best, commit to it, and never look back - no plan, no memory, no revision. Grokking Algorithms puts the strategy in one sentence: “at each step you pick the locally optimal solution, and in the end you’re left with the globally optimal solution.” The important word is sometimes. Your job is to know which problems make that sentence true. The proof is the same exchange argument practiced in the site’s Proofs exercises.

The greedy move

A greedy algorithm has two parts: a choice rule and a refusal to reconsider. The choice rule defines “looks best right now”: take the largest coin, take the cheapest frontier node, take the activity that ends earliest. The refusal separates greedy from other techniques. Once greedy makes a choice, it never revisits it, swaps it out, or saves an alternative “in case.” Sorting is not greedy; it compares everything before placing anything. Greedy decides in one pass and moves on.

That refusal is the key difference between greedy and the site’s Dynamic programming article. Dynamic programming keeps every reasonable option alive and combines them. The coin-change table stores the best answer for every amount below the target, then builds the target’s answer from those results. Greedy makes one choice and destroys the alternatives. The coin-change article’s greedy trap shows this clearly: with coins 1, 3, and 4, making 6, greedy takes a 4 and never looks back, ending with three coins; the optimal two-coin answer, 3 + 3, required keeping the 3 option alive. Dynamic programming is greedy with its options kept, and therefore with its mistakes kept too - it spends memory and time to avoid committing. Greedy commits immediately and risks correctness. The question here is simple: when is that commitment safe?

You already met this technique: Dijkstra

The site taught you a greedy algorithm before this article existed. The Dijkstra’s algorithm article describes its method as a commitment: at every step, take the cheapest unsettled node, declare its distance final, and never revise it. That is the greedy move: make a locally optimal choice, the frontier node with the smallest tentative distance, and make it irrevocable. The article also gives the condition: edge weights must be non-negative. Only then can no later discovery offer a cheaper route to a settled node. A negative edge can provide that cheaper later route, and greedy cannot undo its choice.

That is the general lesson. Greedy algorithms are not simply easier algorithms. They bet the correctness of the entire run on one property of the input. Dijkstra’s bet is “no later route is cheaper.” The algorithms below make bets with the same shape. Check each one by proving that an optimal solution can move toward the greedy choice without losing anything. That proof is the subject of the next section, and it works on the site’s own exercises.

The worked example: earliest finish wins

The classic greedy success story is activity selection. You have activities with start and finish times, and you want the largest set that do not overlap - the largest set of meetings a single room can host. The greedy rule is direct: repeatedly take the available activity that finishes earliest, then discard everything that overlaps it. The Elixir is small enough to read whole:

defmodule Schedule do
  @doc "Largest non-overlapping {start, finish} set, greedy by earliest finish."
  def select(activities) do
    activities
    |> Enum.sort_by(fn {_start, finish} -> finish end)
    |> Enum.reduce({-1, []}, fn {start, finish}, {last_end, chosen} ->
      if start >= last_end,
        do: {finish, [{start, finish} | chosen]},
        else: {last_end, chosen}
    end)
    |> elem(1)
    |> Enum.reverse()
  end
end

Schedule.select([
  {9, 11}, {10, 12}, {11, 13}, {12, 14}, {13, 15}, {14, 16}, {9, 10}
])

The sort puts the earliest-finishing activity first. The fold takes it, records where it ends, and rejects anything that starts before that point. On this input it returns four non-overlapping activities - the maximum possible - because every schedule of three leaves room for a fourth. The rule works for a precise reason: an activity that finishes earliest leaves the most room afterward. If an optimal solution skips it for an activity that starts at the same time but ends later, swap in the earlier-finishing activity. You create room; you do not lose any.

The proof that it stays ahead

That “swap” sentence is the proof technique, and the site’s Induction article gives its shape. Order the greedy picks and the picks of any other valid solution by start time. Claim that, at every position, greedy’s pick ends no later than the other solution’s pick in that position - greedy “stays ahead.” The base case follows from the rule: greedy’s first pick is the earliest-finishing activity, so it ends no later than anyone’s first pick. For the step, suppose greedy’s $k$-th pick ends no later than the other solution’s $k$-th pick. The other solution’s $(k+1)$-th pick starts after its $k$-th pick ends, so it starts after greedy’s $k$-th pick ends too. It was available to greedy at step $k+1$. Greedy chose the available activity that finishes earliest, so greedy’s $(k+1)$-th pick ends no later than the other solution’s $(k+1)$-th pick. Induction keeps the two schedules from crossing.

The conclusion takes one line. If another solution held more activities than greedy, its extra pick would start after greedy’s last pick ended. That activity was available to greedy, so greedy would not have stopped. No valid solution has more activities than the greedy one; the greedy solution is optimal. Keep the exchange: when an optimal solution disagrees with greedy, swap in the greedy choice - the earliest-finishing activity is never worse than the other first choice - and the result remains optimal. Repeat that swap at every disagreement. An optimal solution that is greedy appears.

This is the reasoning behind the site’s Proofs exercises. The What is a proof? article gives the standard: an argument that convinces without leaving a gap. An exchange argument says what any optimal solution looks like, shows that the greedy choice can replace another first choice, and repeats. That is the entire shape. The proof exercises at /proofs exist to make it familiar.

The failure mode: when the local choice forecloses the global one

The greedy promise is conditional. When it fails, the problem is not a bug in the rule. The problem does not support that commitment. The classic counterexample is the 0/1 knapsack: a thief has a capacity-limited bag, items have weights and values, and each item is taken whole or not at all. The tempting greedy rule is “take the most valuable per pound first.” It fails on this tiny input:

capacity = 10
items = [{"gold bar", 6, 24}, {"silver bar", 5, 15}, {"bronze bar", 5, 15}]

items
|> Enum.sort_by(fn {_name, weight, value} -> -value / weight end)
|> Enum.reduce({0, 0, []}, fn {name, weight, value}, {used, total, picked} ->
  if used + weight <= capacity,
    do: {used + weight, total + value, [name | picked]},
    else: {used, total, picked}
end)

The ratios are 4, 3, and 3. Greedy takes the gold bar, worth 24, and cannot fit either remaining bar: weights 6 and 5 exceed the capacity of 10. The optimal answer is silver plus bronze, with weight 10 and value 30. Greedy was right that gold is the best first item. It was wrong that the best first item belongs to the best set. The DP article’s coin change shows the same failure with coins: the optimal answer depends on a combination of choices, and no single choice is responsible.

Ask whether the greedy choice can belong to an optimal solution and still leave the remainder solvable the same way. Activity selection passes. The earliest-finishing activity belongs to some optimal solution, and the remaining activities, those that start after it ends, form the same problem again. The 0/1 knapsack fails: the gold bar is not in the optimal solution, and even when a greedy item is included, the leftover capacity does not behave like a fresh problem. This is why the 0/1 knapsack is the subject of the site’s P vs NP article: it is NP-complete, and greedy is the approximation everyone reaches for anyway - the same “accept approximation, and a greedy or bounded heuristic” move that article describes. The fractional knapsack is greedy-solvable because the thief may take any portion of an item; a fraction of gold never blocks a fraction of silver. Divisibility makes the local choice safe.

The signature: exchange

Two properties make commitment safe, and the worked example has both. The first is optimal substructure - the same property dynamic programming relies on: the best solution to the whole problem contains the best solution to the remainder. The second is the exchange property: adjust any optimal solution toward the greedy choice - swap in the earliest-finishing activity - without making it worse. Together, these properties support the proof above. When a problem has both, greedy is not a heuristic. It is an algorithm with a theorem. When one is missing, greedy is a bet.

The same exchange argument proves the most famous greedy of all, the one that runs your review queue. Earliest due date is the scheduling rule for tasks with deadlines: to minimize the maximum lateness of any task, process tasks in due-date order. The proof is another swap: if a schedule processes task X before task Y even though X is due later, swap them. The maximum lateness cannot increase, so an optimal schedule exists in due-date order. The site’s own scheduler belongs to this family. Its “Up next” list on the home page serves due reviews before reviews still ahead of schedule, because a review that slips past its due date contributes the lateness that matters. The Why this site makes you review article explains why the schedule exists; this article explains why the ordering rule works. Algorithms to Live By devotes a chapter to the same family - scheduling rules like earliest-due-date are optimal for goals such as “minimize the worst lateness” - and it is the rare algorithm book whose theorems survive contact with a to-do list.

The site’s problem: minimum platforms

The site’s interval-scheduling exercise is Minimum Platforms: given train schedules, find the fewest platforms so no two trains share one at the same minute. The greedy shape is the other half of the interval problem. Activity selection asks “how many fit”; this asks “how deep is the pile.” The classic approach sorts the day’s events and sweeps once. An arrival adds a train, a departure frees a platform, and the answer is the counter’s peak. The exercise is filed under sorting for a reason: greedy runs on a sorted spine, and sorting is where this series started.

The site’s version adds a trap that the naive sweep misses: trains may arrive before midnight and depart after it, so a train is still in the station at 00:00 while new trains arrive. The peak counter is no longer the peak of the day. The exercise’s warning states the rule - sorting the day’s times and sweeping once is not enough - and finding the counting that is enough is the hard part, so this article will not give it away. Use the proof’s technique: when a greedy argument breaks, find the input property it assumed without saying so - here, that every train fits inside one day - and ask where the count can actually change.

Where to go next

• Minimum Platforms - interval scheduling with the midnight trap; the greedy shape plus the hard part this article leaves to you.
• Dijkstra’s algorithm: when every hop costs something
  • the site’s first greedy, and the fine print (negative weights) that marks its boundary.
• Dynamic programming: recursion with a cache
  • the technique that keeps the options greedy destroys; its coin-change trap is this article’s failure mode in another costume.
• P vs NP: when a thousand cores won’t help
  • why some problems (0/1 knapsack) have no greedy theorem, and approximation is the honest fallback.
• What is a proof? and Induction - the exchange argument is an induction; the proof exercises at /proofs practice exactly this shape.
• Why this site makes you review
  • the schedule that earliest-due-date orders: your own review queue.
• Algorithms past the interview
  • naming the technique (and the property that makes it safe) is the class-recognition move interviews and production both reward.

Greedy algorithms are commitment. Commitment is useful only when the exchange argument holds. Do not stop at spotting a “greedy problem.” Ask which property makes the local choice safe, just as Dijkstra’s non-negative weights and activity selection’s earliest finish do. When that property exists, greedy is a one-line algorithm with a theorem behind it. When it does not, the same one-liner is a bet against the input. Knowing which case you have is the technique, not the one-liner.