---
title: The Greedy Method
module: Greedy Algorithms
moduleNumber: 7
lessonNumber: 1
order: 701
summary: |
  A greedy algorithm builds a solution one locally-best choice at a time and
  never looks back. We isolate the two properties that make this work — the
  greedy-choice property and optimal substructure — prove the canonical
  activity-selection algorithm correct with an exchange argument, watch greedy
  fail on the 0/1 knapsack, and glimpse matroids as the theory
  that says exactly when the greedy method is optimal.
topics: [Greedy Algorithms]
sources:
  - book: CLRS
    ref: "Ch. 16 — Greedy Algorithms"
  - book: Skiena
    ref: "§1.4 & §5 — Heuristics; Weighted Graph Algorithms"
  - book: Erickson
    ref: "Ch. 4 — Greedy Algorithms"
practice:
  - title: 'Assign Cookies'
    slug: assign-cookies
    difficulty: Easy
  - title: 'Jump Game'
    slug: jump-game
    difficulty: Medium
  - title: 'Jump Game II'
    slug: jump-game-ii
    difficulty: Medium
  - title: 'Gas Station'
    slug: gas-station
    difficulty: Medium
  - title: 'Non-overlapping Intervals'
    slug: non-overlapping-intervals
    difficulty: Medium
  - title: 'Task Scheduler'
    slug: task-scheduler
    difficulty: Medium
---

A **greedy algorithm** builds up a solution piece by piece, and at every step it
takes the option that looks best _right now_ (the largest, the smallest, the
cheapest, the soonest), ignoring the choices still to come and never revisiting
a choice already made. The bet is that locally optimal choices add up to a
globally optimal solution.

Sometimes the bet pays off, and the result is a simple and fast algorithm.
Often it does not, and the algorithm returns wrong answers. The central task of
the greedy method is telling the two cases apart, and the only reliable way
is a **proof**. Erickson puts the warning bluntly: most greedy algorithms
are _wrong_, and a greedy strategy that has not been proved correct should be
treated as a plausible guess, nothing more.[^erickson-greedy]

## What makes greedy work

[Dynamic programming](/algorithms/dynamic-programming/principles), which we meet in a later module, considers _all_ the ways a
problem decomposes and picks the best. Greedy algorithms commit
to one choice immediately and recurse on what remains. Two structural properties
make that commitment valid.

- **The greedy-choice property.**[^clrs-greedy] There exists an optimal solution that contains
  the greedy (locally optimal) first choice. We never have to look ahead: a
  best-looking-now choice is _safe_, since some optimal solution agrees with it.
- **Optimal substructure.** After making the greedy choice, what remains is a
  smaller instance of the _same problem_, and an optimal solution to the whole
  is the greedy choice plus an optimal solution to that subproblem.

Optimal substructure is shared with dynamic programming. The greedy-choice
property is the extra ingredient: it collapses the many subproblems DP would explore
down to a _single_ one. That is why greedy algorithms, when they work, are so
much faster than their DP cousins. Proving these two properties, not running
the code on a few examples, is what separates a correct greedy algorithm from a
hopeful heuristic.

## The canonical example: activity selection

We are given $n$ **activities**
that compete for one resource: a lecture hall, a tennis court,
a single CPU. Activity $i$ has a start time $s_i$ and a finish time $f_i$, and
occupies the half-open interval $[s_i, f_i)$. Two activities are **compatible**
if their intervals do not overlap. We want to select a largest possible set of
mutually compatible activities.

> **Input:** activities $1, \dots, n$ with start/finish times $s_i < f_i$.
> **Output:** a maximum-size set $S$ of pairwise compatible activities.

Drawn on a number line, an instance and one optimal schedule look like this. The
shaded bars are the chosen activities; they tile the timeline without overlap.

$$
% caption: Timeline of activities as interval bars with a maximum compatible set shaded.
\begin{tikzpicture}[xscale=0.62, yscale=0.62,
  act/.style={draw, thick, minimum height=5mm, fill=black!8},
  chosen/.style={draw=acc, very thick, minimum height=5mm, fill=acc!15}]
  \definecolor{acc}{HTML}{2348F2}
  % time axis
  \draw[->, thick] (0,-0.6) -- (13,-0.6) node[right] {time};
  \foreach \x in {0,1,...,12} \draw (\x,-0.5) -- (\x,-0.7) node[below=2pt, font=\tiny] {\x};
  % activities: each node spans [s,f) drawn as a bar
  \node[chosen, minimum width=2cm] at (1,5) {$a$};   % [0,2)
  \node[act,    minimum width=3cm] at (2.5,4) {$b$}; % [1,4)
  \node[chosen, minimum width=2cm] at (4,3) {$c$};   % [3,5)
  \node[act,    minimum width=4cm] at (5,2) {$d$};   % [3,7)
  \node[chosen, minimum width=2cm] at (6,1) {$e$};   % [5,7)
  \node[chosen, minimum width=3cm] at (8.5,4) {$g$}; % [7,10)
  \node[act,    minimum width=4cm] at (9,0) {$h$};   % [7,11)
\end{tikzpicture}
$$

The chosen set $\{a, c, e, g\}$ uses four activities; no compatible set is
larger. The question is _which_ greedy rule finds such a set.

### Choosing the right greedy rule

Several plausible rules suggest themselves, and most are wrong:

- _Earliest start first?_ A single activity that starts at time $0$ but runs
  forever blocks everything — wrong.
- _Shortest duration first?_ A short activity wedged between two longer ones can
  knock out two compatible activities to gain one — wrong.
- _Fewest conflicts first?_ Tempting, but constructible counterexamples defeat
  it too.

Two of these failures are easy to picture. Earliest-start picks the long bar
that blocks the whole timeline; shortest-job picks the short middle bar that
displaces both of its neighbors.

$$
% caption: Two greedy rules that fail activity selection. Top, earliest-start: a single
%          early-starting job (red) blocks three compatible ones (green). Bottom,
%          shortest-duration: a short job (red) evicts the two longer jobs (green)
%          flanking it.
\begin{tikzpicture}[xscale=0.6, yscale=0.62,
  bar/.style={draw, thick, minimum height=4.5mm},
  bad/.style={draw=red!75!black, very thick, minimum height=4.5mm, fill=red!18},
  good/.style={draw=acc, very thick, minimum height=4.5mm, fill=acc!15}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-4.6,0.5) rectangle (8.0,6.1);
  % --- earliest start ---
  \node[font=\footnotesize, align=right] at (-3.4,5.5) {earliest\\start};
  \node[bad, minimum width=6cm] at (3,5.5) {picks this};
  \node[good, minimum width=1.6cm] at (0.8,4.6) {};
  \node[good, minimum width=1.6cm] at (3,4.6) {};
  \node[good, minimum width=1.6cm] at (5.2,4.6) {};
  \draw[->, thick] (-0.3,3.9) -- (6.3,3.9);
  % --- shortest duration ---
  \node[font=\footnotesize, align=right] at (-3.4,2.0) {shortest\\job};
  \node[good, minimum width=2.4cm] at (1.4,2.0) {};
  \node[bad, minimum width=1.3cm] at (3.05,2.0) {};
  \node[good, minimum width=2.4cm] at (4.7,2.0) {};
  \node[red!75!black, font=\footnotesize] at (3.05,2.9) {picks this};
  \draw[->, thick] (-0.3,1.0) -- (6.3,1.0) node[right, font=\footnotesize] {time};
\end{tikzpicture}
$$

The rule that works is **earliest finish time first**: repeatedly pick the
compatible activity that finishes soonest.[^clrs-activity] The intuition:
finishing early frees the hall as soon as possible, leaving the most room for
everything that follows. This is the crux of [interval scheduling](/algorithms/greedy/scheduling-and-intervals).

```algorithm
caption: $\textsc{Greedy-Activity-Select}(s, f)$ — choose a max set of compatible activities
number: 1
sort activities so that $f_1 \le f_2 \le \cdots \le f_n$
$S \gets \set{1}$ // earliest finish is safe
$k \gets 1$ // last activity added to $S$
for $m \gets 2$ to $n$ do
  if $s_m \ge f_k$ then // $m$ starts after $k$ finishes
    $S \gets S \cup \set{m}$
    $k \gets m$
return $S$
```

After the one-time sort by finish time, a single linear scan does the rest:
$\Theta(n)$ work, for $\Theta(n \log n)$ total, dominated entirely by the sort.
If the finish times arrive already sorted, the selection itself is linear.

Run the scan on the instance above. Sorting the seven activities by finish
time gives the order $a(f{=}2),\,b(4),\,c(5),\,d(7),\,e(7),\,g(10),\,h(11)$. The
scan keeps a single number, $f_k$, the finish time of the last accepted
activity, and admits the next activity exactly when its start is at least $f_k$.

| Step | Activity | $[s, f)$ | $f_k$ before | $s \ge f_k$? | Action |
| --- | --- | --- | --- | --- | --- |
| 1 | $a$ | $[0, 2)$ | — | — | accept, $f_k \gets 2$ |
| 2 | $b$ | $[1, 4)$ | $2$ | $1 \ge 2$? no | reject |
| 3 | $c$ | $[3, 5)$ | $2$ | $3 \ge 2$? yes | accept, $f_k \gets 5$ |
| 4 | $d$ | $[3, 7)$ | $5$ | $3 \ge 5$? no | reject |
| 5 | $e$ | $[5, 7)$ | $5$ | $5 \ge 5$? yes | accept, $f_k \gets 7$ |
| 6 | $g$ | $[7, 10)$ | $7$ | $7 \ge 7$? yes | accept, $f_k \gets 10$ |
| 7 | $h$ | $[7, 11)$ | $10$ | $7 \ge 10$? no | reject |

The scan accepts $\{a, c, e, g\}$, the four-activity optimum drawn earlier. Each
rejection happens because the candidate starts before the hall is free again; each
acceptance advances $f_k$ to the new, later finish. The figure below traces the
same run, marking every activity as accepted (blue) or rejected (struck through)
in finish-time order.

$$
% caption: Earliest-finish scan on the seven-activity instance. Activities are laid out in
%          finish-time order; blue bars are accepted, gray struck-through bars rejected.
%          The dashed line marks f_k, the finish of the last accepted activity, after each step.
\begin{tikzpicture}[xscale=0.62, yscale=0.6,
  acc/.style={very thick, minimum height=5mm},
  rej/.style={draw=black, thick, minimum height=5mm, fill=black!6}]
  \definecolor{accc}{HTML}{2348F2}
  \draw[->, thick] (0,-0.6) -- (12.5,-0.6) node[right] {time};
  \foreach \x in {0,2,4,6,8,10,12} \draw (\x,-0.5) -- (\x,-0.7) node[below=1pt, font=\tiny] {\x};
  % rows top to bottom in finish order; accepted bars in blue
  \node[acc, draw=accc, fill=accc!15, minimum width=2cm] at (1,5)   {$a$};   % [0,2) accept
  \node[rej, minimum width=3cm]   at (2.5,4) {};   % [1,4) reject
  \node[font=\small] at (1.55,4) {$b$};
  \draw[black] (2.1,4.3) -- (3.85,3.7);
  \node[acc, draw=accc, fill=accc!15, minimum width=2cm] at (4,3)   {$c$};   % [3,5) accept
  \node[rej, minimum width=4cm]   at (5,2)   {};   % [3,7) reject
  \node[font=\small] at (3.55,2) {$d$};
  \draw[black] (4.15,2.3) -- (6.85,1.7);
  \node[acc, draw=accc, fill=accc!15, minimum width=2cm] at (6,1)   {$e$};   % [5,7) accept
  \node[acc, draw=accc, fill=accc!15, minimum width=3cm] at (8.5,0) {$g$};   % [7,10) accept
  \node[rej, minimum width=4cm]   at (9,-1)  {};   % [7,11) reject
  \node[font=\small] at (7.55,-1) {$h$};
  \draw[black] (8.15,-0.7) -- (10.85,-1.3);
\end{tikzpicture}
$$

::impl{algo="activity_selection"}

## Correctness by the exchange argument

The usual proof technique for greedy algorithms is the **exchange
argument**: take any optimal solution, and show you can _transform_ it, swapping
one of its choices for the greedy choice, without making it worse. Since the
result is no worse, it is still optimal, and it now agrees with greedy on the
first choice. That establishes the greedy-choice property; optimal substructure
then finishes the job by induction.

> **Lemma (Greedy choice).** Let activity $1$ be the activity with the earliest
> finish time. Then some maximum-size compatible set contains activity $1$.

> **Proof.** Let $S^\star$ be any optimal solution, and let $j$ be the activity in
> $S^\star$ with the earliest finish time. If $j = 1$ we are done. Otherwise,
> build $S' = (S^\star \setminus \set{j}) \cup \set{1}$ — evict $j$, admit $1$.
>
> We must check $S'$ is still a valid schedule. Activity $1$ finishes no later
> than $j$, because $1$ has the globally earliest finish: $f_1 \le f_j$. Every
> other activity $i \in S^\star$ was compatible with $j$, so it started after $j$
> finished, $s_i \ge f_j \ge f_1$. Hence $i$ is compatible with $1$ as well. So
> $S'$ is a set of pairwise compatible activities, and
>
> $$
> \abs{S'} = \abs{S^\star} - 1 + 1 = \abs{S^\star}.
> $$
>
> $S'$ is just as large as the optimum, so it is itself optimal — and it contains
> activity $1$. $\qed$

The picture of the swap is the whole argument in one image. Activity $1$ slides in where
$j$ was, finishing at least as early, so nothing downstream can break.

$$
% caption: Exchange argument swapping activity $j$ for the earliest-finishing activity
%          $1$.
\begin{tikzpicture}[xscale=0.6, yscale=0.6,
  bar/.style={draw, thick, minimum height=5mm},
  chosen/.style={draw=acc, very thick, minimum height=5mm, fill=acc!15}]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->, thick] (0,-0.6) -- (11,-0.6) node[right] {time};
  % top row: original optimal S* uses j, then a later activity
  \node[bar, minimum width=3cm] at (1.5,2) {$j$};        % [0,3)
  \node[bar, minimum width=2.8cm] at (5.4,2) {rest of opt}; % [4,...)
  % bottom row: swapped S' uses 1 (finishes earlier) in place of j
  \node[chosen, minimum width=2cm] at (1,0.4) {$1$};     % [0,2)
  \node[bar, minimum width=2.8cm] at (5.4,0.4) {rest of opt};
  \draw[->, very thick, red!75!black] (2.6,1.65) to[bend left=18] (1.55,0.95);
  \node[red!75!black, font=\footnotesize] at (4.6,1.05) {swap in};
\end{tikzpicture}
$$

With the greedy-choice lemma in hand, **optimal substructure** completes the
proof by induction.

> **Proof (optimality, by substructure).** After committing to activity $1$, every
> remaining feasible activity must start at or after $f_1$; the leftover problem is
> just activity selection on that smaller set, which the same rule solves optimally
> by the induction hypothesis. The greedy choice plus the optimal subsolution is
> optimal for the whole. $\qed$

This two-step shape, **(1)** an exchange argument for the greedy-choice
property and **(2)** induction via optimal substructure, is the template for
_every_ greedy correctness proof in this course, [Huffman codes](/algorithms/greedy/huffman-codes) and [minimum
spanning trees](/algorithms/graphs/minimum-spanning-trees) included.

## When greedy fails: the 0/1 knapsack

Greedy does not always work; the standard counterexample is the
**knapsack problem**. We have a knapsack of capacity $W$ and $n$ items, item $i$
having weight $w_i$ and value $v_i$. We want the most valuable load that fits.

In the **fractional knapsack**, we may take _any fraction_ of an item. Here
greed works perfectly: sort by value density $v_i / w_i$, and greedily fill with
the densest item, taking a fraction of the last one to top off the capacity
exactly.[^skiena-greedy] An exchange argument proves it: any optimal solution that takes less
of a denser item and more of a sparser one can be nudged toward the greedy
choice without losing value.

Run the density rule concretely. Take capacity $W = 50$ and three items, already
listed in decreasing density:

| Item | Weight $w_i$ | Value $v_i$ | Density $v_i/w_i$ |
| --- | --- | --- | --- |
| 1 | 10 | 60 | 6.0 |
| 2 | 20 | 100 | 5.0 |
| 3 | 30 | 120 | 4.0 |

Greedy takes item $1$ whole (using $10$ of $50$, value $60$), then item $2$ whole
(using $30$ of $50$, value $160$), then only a _fraction_ of item $3$: $20$ of its
$30$ units fit, so it takes $\tfrac{20}{30} = \tfrac{2}{3}$ of it for
$\tfrac{2}{3}\cdot 120 = 80$ more value. The load is worth $60 + 100 + 80 = 240$,
and the capacity is filled exactly. No division of these items into the sack does
better, because every unit of weight we spend goes on the densest value still
available — the moment a fraction of item $3$ replaces any unit already taken, the
total can only drop.

$$
% caption: The fractional-knapsack greedy fill ($W=50$). Items enter in density order:
%          item 1 ($6.0$) and item 2 ($5.0$) whole, then $\tfrac23$ of item 3 ($4.0$) tops
%          off the capacity exactly, for value $240$.
\begin{tikzpicture}[yscale=0.5, xscale=0.9, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \draw[thick] (0,0) rectangle (2,10);
  \foreach \y in {2,4,6,8} \draw[black] (0,\y) -- (2,\y);
  % item 1: weight 10 -> 2 units of 10; item 2: weight 20 -> 4 units; item 3 frac 20 -> 4 units
  \fill[acc!30, draw=black, thick] (0,0) rectangle (2,2);
  \fill[acc!20, draw=black, thick] (0,2) rectangle (2,6);
  \fill[acc!10, draw=black, thick] (0,6) rectangle (2,10);
  \node[font=\footnotesize] at (1,1) {item 1: $60$};
  \node[font=\footnotesize] at (1,4) {item 2: $100$};
  \node[font=\footnotesize, align=center] at (1,8) {$\tfrac23$ of item 3:\\ $80$};
  \node[right, font=\footnotesize] at (2.2,5) {value $= 240$};
  \node[below, font=\footnotesize] at (1,-0.3) {capacity $W=50$ f\/illed};
\end{tikzpicture}
$$

In the **0/1 knapsack**, each item is all-or-nothing: take it whole or leave it.
And here the _same_ density rule collapses. Consider $W = 10$ and:

| Item | Weight | Value | Density $v/w$ |
| --- | --- | --- | --- |
| 1 | 6 | 12 | 2.0 |
| 2 | 5 | 9 | 1.8 |
| 3 | 5 | 9 | 1.8 |

Greedy by density grabs item $1$ (value $12$, weight $6$), then _cannot_ fit
either remaining item, since both need weight $5$ but only $4$ is left. It returns
value $\mathbf{12}$. Yet items $2$ and $3$ together weigh exactly $10$ and are
worth $\mathbf{18}$. Greedy is far from optimal.

$$
% caption: Greedy by density on the 0/1 knapsack ($W=10$). Left, greedy grabs the densest
%          item $1$ ($w=6$), stranding $4$ units of unusable capacity for value $12$.
%          Right, the optimum packs items $2$ and $3$ ($w=5$ each) for value $18$.
\begin{tikzpicture}[yscale=0.5, xscale=0.9, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  % left knapsack: greedy
  \draw[thick] (0,0) rectangle (2,10);
  \foreach \y in {2,4,6,8} \draw[black] (0,\y) -- (2,\y);
  \fill[red!18, draw=black, thick] (0,0) rectangle (2,6);
  \node at (1,3) {item $1$};
  \node[font=\footnotesize, fill=white, inner sep=1.5pt] at (1,1.0) {$w=6$, $v=12$};
  \node[red!75!black, font=\footnotesize, align=center] at (1,8) {wasted\\$4$ units};
  \node[below=1pt, font=\footnotesize] at (1,0) {greedy: value $12$};
  \node[above, font=\footnotesize] at (1,10) {density rule};
  % right knapsack: optimal
  \begin{scope}[xshift=4cm]
    \draw[thick] (0,0) rectangle (2,10);
    \foreach \y in {2,4,6,8} \draw[black] (0,\y) -- (2,\y);
    \fill[acc!22, draw=black, thick] (0,0) rectangle (2,5);
    \fill[acc!12, draw=black, thick] (0,5) rectangle (2,10);
    \node at (1,2.5) {item $2$};
    \node at (1,7.5) {item $3$};
    \node[font=\footnotesize, fill=white, inner sep=1.5pt] at (1,1.0) {$w=5$, $v=9$};
    \node[font=\footnotesize, fill=white, inner sep=1.5pt] at (1,6.0) {$w=5$, $v=9$};
    \node[below=1pt, font=\footnotesize] at (1,0) {optimal: value $18$};
    \node[above, font=\footnotesize] at (1,10) {best f\/it};
  \end{scope}
\end{tikzpicture}
$$

> **Remark (Greedy-choice failure).** What fails is the **greedy-choice property**. Taking the densest
> item is _not_ safe: no swap recovers an optimal solution that contains it,
> because the indivisible weight it consumes can strand the capacity it leaves
> behind. The leftover space, not just the leftover items, depends on the whole
> combination — so the choice cannot be made locally.

This is where the boundary between greedy and dynamic programming falls. The 0/1
knapsack has optimal substructure but _lacks_ the greedy-choice property, so it
needs DP, which considers both alternatives (take item $i$ or skip it) rather
than committing to one. The fractional version restores the greedy-choice
property because a fraction can always absorb the leftover capacity exactly,
leaving no stranded space.

::impl{algo="fractional_knapsack"}

## When _is_ greed good? A glimpse of matroids

For a large family of problems there is a theorem of the form "greedy is
optimal exactly when…", and its language is the
[**matroid**](/algorithms/greedy/matroids).

A matroid is a pair $(E, \mathcal{I})$ built from a finite ground set $E$ and a family
$\mathcal{I}$ of "independent" subsets, satisfying two axioms:

- **Heredity.** If $A \in \mathcal{I}$ and $B \subseteq A$, then
  $B \in \mathcal{I}$. (Subsets of independent sets are independent.)
- **Exchange.** If $A, B \in \mathcal{I}$ and $\abs{A} < \abs{B}$, then some
  element $x \in B \setminus A$ has $A \cup \set{x} \in \mathcal{I}$. (A smaller
  independent set can always be grown using an element of a larger one.)

The forests of a graph form a matroid: subsets of a forest are forests, and a
smaller forest can always borrow an edge from a larger one without making a
cycle.

$$
% caption: The graphic matroid's exchange property. Forest $A$ (two edges) is smaller than
%          some larger forest $B$; an edge of $B$ (blue) joins two of $A$'s trees without
%          making a cycle, growing $A$.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6mm, inner sep=1pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (a1) at (0,1.4) {$1$};
  \node (a2) at (1.4,1.4) {$2$};
  \node (a3) at (0,0) {$3$};
  \node (a4) at (1.4,0) {$4$};
  \node[draw=none] at (0.7,2.2) {forest $A$};
  \draw[thick] (a1) -- (a2);
  \draw[thick] (a3) -- (a4);
  \draw[acc, very thick] (a2) -- (a4);
  \node[draw=none, text=acc, font=\footnotesize] at (3.2,0.7) {add edge 2-4};
  \node[draw=none, text=acc, font=\footnotesize] at (3.2,0.1) {(no cycle)};
\end{tikzpicture}
$$

The headline result is due to Rado and Edmonds.

> **Theorem (Rado–Edmonds).** The greedy algorithm computes a maximum-weight
> independent set if and only if the structure is a matroid.[^clrs-matroid]

This theorem is why Kruskal's minimum
spanning tree algorithm, which greedily adds the cheapest edge that creates no cycle,
is correct: it is greedy on the graphic matroid. Activity selection, too, can be
cast as greedy on a matroid.

Matroids do not cover _every_ successful greedy algorithm; Huffman coding, our
next lesson, falls outside the theory. But they explain a large class and
sometimes reduce the correctness question to a checkable condition. We will not
develop the theory further here; the exchange axiom that defines it is the same
exchange idea used in our correctness proofs.

::impl{algo="matroid_greedy"}

## A recipe for greedy algorithms

Drawing the standard references together, the workflow is always the same:

1. **Cast the problem** as a sequence of choices, where each choice leaves a
   smaller subproblem of the same kind.
2. **Guess a greedy rule** — the locally optimal choice. Beware: the _obvious_
   rule is often wrong (recall the failed activity-selection rules).
3. **Prove the greedy-choice property** with an exchange argument: any optimal
   solution can be transformed to contain the greedy choice.
4. **Prove optimal substructure** and combine, by induction, into a full proof.

If steps 3 and 4 go through, the result is a correct, usually fast, usually
simple algorithm. If they do not, use dynamic programming instead.

## When greedy is only _approximately_ optimal

CLRS frames greedy as a route to _exact_ optima, and this lesson has
kept to that: activity selection and the fractional knapsack are solved to
optimality, or greed is abandoned. But the greedy method also serves as an
**approximation algorithm** — a fast heuristic that is
provably _close_ to optimal even when finding the true optimum is intractable.

**Set cover and the $\ln n$ guarantee.** Given a universe of $n$ elements and a
family of sets, **set cover** asks for the fewest sets whose union is everything.
It is NP-hard, so no efficient exact algorithm is expected. The natural greedy
rule — repeatedly take the set covering the most still-uncovered elements — returns
a cover using at most $H_n = 1 + \tfrac12 + \cdots + \tfrac1n \le \ln n + 1$ times
as many sets as the optimum.[^greedy-setcover] The $(\ln n)$ factor is tight:
Dinur and Steurer (2014) proved that no
polynomial-time algorithm beats $(1-o(1))\ln n$ unless $\mathrm{P} = \mathrm{NP}$,
so greedy is essentially the _best possible_ approximation.[^greedy-dinur] The
same logarithmic greedy bound governs its twin, **vertex cover** by the
maximum-degree rule, which is why set-cover-shaped problems (facility
placement, feature selection, test-suite minimization) are usually attacked
greedily first.

$$
% caption: Greedy set cover. Each round takes the set covering the most still-uncovered
%          elements (blue); after three greedy picks the universe of $10$ is covered. The
%          greedy cover is at most $H_n \approx \ln n$ times the optimum.
\begin{tikzpicture}[font=\small, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % 10 elements as dots in a row, covered progressively
  \foreach \i in {0,...,9} \node[draw, circle, minimum size=4mm, inner sep=0] at (\i*0.72,0) {};
  \node[anchor=west, font=\footnotesize] at (7.4,0) {universe, $n=10$};
  % round 1: pick covers 5
  \draw[acc, thick] (-0.28,-0.32) rectangle (2.6,0.32);
  \node[acc, font=\footnotesize, anchor=north] at (1.15,-0.4) {pick 1: covers 5};
  % round 2: pick covers 3
  \draw[acc, thick] (2.9,-0.32) rectangle (4.75,0.32);
  \node[acc, font=\footnotesize, anchor=north] at (3.8,-0.4) {pick 2: 3};
  % round 3: pick covers 2
  \draw[acc, thick] (5.05,-0.32) rectangle (6.5,0.32);
  \node[acc, font=\footnotesize, anchor=north] at (5.75,-0.4) {pick 3: 2};
\end{tikzpicture}
$$

**Online greedy and the competitive ratio.** When the input arrives one piece at
a time and each decision is irrevocable — an **online** problem — greedy is often
the only option, and its quality is measured by the **competitive ratio**, the
worst-case ratio of the online cost to the best offline (all-knowing) cost. The
canonical case is **caching / paging**: on a cache miss, which page do you evict?
Sleator and Tarjan (1985) showed that any deterministic online eviction policy is
at best $k$-competitive for a cache of size $k$, and that the greedy-flavored
**Least-Recently-Used** achieves that optimal $k$, while their **competitive
analysis** framework became the standard one for online algorithms.[^greedy-st]
Greedy, in short, is both a route to exact optima and the natural — sometimes
provably optimal — strategy when the input is revealed online.

## Takeaways

- A **greedy algorithm** makes the locally optimal choice at each step and never
  reconsiders. It is fast and simple, _when it is correct_.
- Correctness needs two properties: the **greedy-choice property** (some optimal
  solution contains the greedy choice) and **optimal substructure** (what
  remains is the same problem, smaller).
- **Activity selection** by earliest finish time is the canonical win; its proof
  is the template **exchange argument** plus induction. Cost: $\Theta(n\log n)$,
  all in the sort.
- The **0/1 knapsack** is the canonical failure: it lacks the greedy-choice
  property, so greed strands capacity and needs dynamic programming instead. Its
  _fractional_ cousin restores the property and yields to greed.
- **Matroids** characterize a broad class where greedy is provably optimal
  (Kruskal's MST among them), a formalization of the exchange argument itself.

[^erickson-greedy]: **Erickson**, Ch. 4 — Greedy Algorithms: the warning that most greedy strategies are wrong and must be proved correct, not merely tested.
[^clrs-greedy]: **CLRS**, Ch. 16 — Greedy Algorithms (§16.2): the greedy-choice property as one of the two ingredients licensing a greedy algorithm.
[^clrs-activity]: **CLRS**, Ch. 16 — Greedy Algorithms (§16.1): the activity-selection problem solved by repeatedly choosing the earliest-finishing compatible activity.
[^skiena-greedy]: **Skiena**, §1.4 & §5 — Heuristics; Weighted Graph Algorithms: the fractional knapsack solved greedily by value density.
[^clrs-matroid]: **CLRS**, Ch. 16 — Greedy Algorithms (§16.4): the Rado–Edmonds theorem that greedy yields a maximum-weight independent set exactly when the structure is a matroid.
[^greedy-setcover]: **CLRS**, Ch. 35 — Approximation Algorithms (§35.3): the greedy set-cover algorithm and its proof of an $H_n \le \ln n + 1$ approximation ratio. The original analysis is **Johnson, D. S.** (1974), "Approximation algorithms for combinatorial problems," _J. Computer and System Sciences_ 9(3), 256–278.
[^greedy-dinur]: **Dinur, I. & Steurer, D.** (2014), "Analytical approach to parallel repetition," _STOC 2014_, 624–633 — establishes that set cover cannot be approximated to better than $(1-o(1))\ln n$ in polynomial time unless $\mathrm{P}=\mathrm{NP}$, matching the greedy bound.
[^greedy-st]: **Sleator, D. D. & Tarjan, R. E.** (1985), "Amortized efficiency of list update and paging rules," _Communications of the ACM_ 28(2), 202–208 — introduces competitive analysis and proves LRU is $k$-competitive for a size-$k$ cache, the best possible for a deterministic policy.