Greedy Algorithms

A greedy algorithm builds a solution one choice at a time. At every step it picks the option that looks best right now, never undoing that choice later. The hope is that a sequence of locally optimal choices produces a globally optimal answer.

Greedy methods are often short and run in near-linear time once the input is sorted, but they are not a universal recipe. The same style of choice that works for activity selection fails for the 0/1 knapsack problem; the right tool there is dynamic programming. This note states when the greedy method is sound, proves the classical activity-selection algorithm, and lists the other GATE syllabus algorithms that are greedy under the hood.

Dynamic programming also needs optimal substructure, but it considers every feasible choice at a subproblem. Greedy commits to one choice and never revisits it. That is why greedy code is usually faster when it works, and why a missing proof is dangerous.

Greedy versus dynamic programming. Both need optimal substructure. Greedy needs the stronger greedy-choice property so that one locally best option is always safe. If that property fails, DP (or another method) is required.

Most greedy proofs, including every proof in this note and in Huffman Coding and Optimal Merge Patterns, follow one template.

The whole proof rests on step 3. When a proposed rule fails, it is step 3 that breaks, and the failure usually points straight to a counterexample.

Pseudocode uses 1-based arrays, <- for assignment and A[i..j] for the subarray from position $i$ to position $j$.

Input. $n$ activities $a_1, \ldots, a_n$, each with a start time $s_i$ and a finish time $f_i$, already sorted so that $f_1 \le f_2 \le \cdots \le f_n$.

Output. A largest set of mutually compatible activities (no two overlap: $a_i$ and $a_j$ with $i < j$ are compatible when $f_i \le s_j$).

The displayed procedure assumes n>=1; an empty-input wrapper returns the empty set when n=0, before accessing a_1.

Best / average / worst time. $\Theta(n)$ after the $O(n \lg n)$ sort that puts finish times in order. Space $\Theta(1)$ beyond the output set (or $\Theta(n)$ if the set is materialised).

Edge cases. $n = 0$ returns the empty set; $n = 1$ returns $\{a_1\}$. Activities that touch at an endpoint ($f_i = s_j$) are treated as compatible, matching the usual GATE convention; if a problem forbids touching, change the test to s[m] > f[k].

Input. $n$ items with weights $w_i > 0$ and values $v_i \ge 0$, and a capacity $W$. Any fraction of an item may be taken.

Greedy rule. Sort by density $v_i / w_i$ descending. Fill the knapsack from the densest item; take a fraction of the first item that does not fit wholly.

Cost model and cases. Assume $n\ge0$, $W\ge0$, constant-time arithmetic, density comparisons and indexed accesses, and mutable item records. After sorting, for $n\ge1$ the scan takes $\Theta(1)$ best time (the first item exceeds the remaining capacity) and $\Theta(n)$ worst time; its average needs a distribution of weights and capacity. Empty input takes $\Theta(1)$. The scan uses $O(1)$ auxiliary words and returns one scalar; storing a fraction for every item would instead require $\Theta(n)$ output words. Sort time and workspace are additional: for example, standard nonadaptive bottom-up mergesort takes $\Theta(n\lg(n+1))$ time and $\Theta(n)$ scratch words in best, average and worst cases for $n\ge1$, excluding the input and scalar output (constant for empty input). An in-place sort has its own workspace bound. The 0/1 version (an item is taken whole or not at all) is not solved by this rule; see DP: 0/1 Knapsack and Matrix-Chain.

Related material. Scheduling every activity into as few rooms as possible is the interval-colouring problem. Sort all $2n$ endpoints by time, with finishes before starts at equal times (touching intervals are compatible); scan left to right, opening a room at each start and freeing one at each finish, and track the peak active count. The number of rooms needed equals the maximum depth (how many activities are live at once). Time $O(n \lg n)$. It belongs with activity selection but is not a separate syllabus item.

Claim. There exists an optimal solution that contains the activity $a_1$ of earliest finish time.

Proof. Let $A$ be any optimal solution and let $a_j$ be the activity in $A$ of earliest finish time. If $a_j = a_1$ we are done. Otherwise replace $a_j$ by $a_1$. Because $f_1 \le f_j$, activity $a_1$ finishes no later than $a_j$ and therefore conflicts with no activity of $A \setminus \{a_j\}$ that $a_j$ did not already conflict with. The new set has the same size and is feasible, so it is optimal and contains $a_1$.

After choosing $a_1$, every remaining feasible activity starts at or after $f_1$. The problem on that subset is again an activity-selection instance. An optimal solution for the original problem is $\{a_1\}$ union an optimal solution of the residual instance. The inductive combination of the greedy-choice property and optimal substructure proves that GREEDY-ACTIVITY-SELECTOR returns an optimal set (CLRS 3e, Section 16.1).

Suppose an optimal packing takes a smaller fraction of a denser item $i$ than of a less dense item $j$. Transferring weight from $j$ to $i$ cannot decrease the total value, and eventually yields a packing that fills denser items first. Hence some optimal packing agrees with the greedy order.

Activities sorted by finish time:

Result $A = \{a_1, a_4, a_5\}$, size 3. Checking all $2^6 = 64$ subsets confirms that no compatible set has 4 activities. The optimum is not unique: $\{a_2, a_4, a_5\}$ is the only other compatible set of size 3. Greedy returns one optimal set, not all of them.

Items $(v, w)$: $(60, 10)$, $(100, 20)$, $(120, 30)$; capacity $W = 50$. Densities $6$, $5$, $4$. Take all of the first two items (weight 30, value 160) and $20/30$ of the third (value 80). Total value $240$. The 0/1 optimum on the same instance is only $220$ (items 2 and 3), so the fractional and 0/1 answers differ.

Coins $\{1, 3, 4\}$, amount 6. Largest-first greedy takes $4 + 1 + 1$ (three coins). Optimal is $3 + 3$ (two coins). Greedy fails because the denominations are not a canonical coin system.

Each of $n$ jobs takes one unit of time, has a deadline $d_i$ (it must finish by time $d_i$) and earns profit $p_i$ only if it meets its deadline. One job runs at a time. Greedy rule: consider jobs in decreasing order of profit, and place each one in the latest free unit slot $t \le d_i$; if no such slot is free, reject it. A set of jobs is feasible exactly when, for every $t$, at most $t$ of its jobs have deadline $\le t$. This structure is what makes the exchange argument work.

Schedule by time slot: $J_4, J_3, J_1, J_2$, total profit $20+25+35+30 = 110$. Checking all $2^7$ subsets confirms 110 is the maximum. The simple slot search costs $O(n^2)$ in the worst case after an $O(n \lg n)$ sort. With a disjoint-set structure that points every slot to the latest free slot at or before it, the search drops to near-linear time.

Placing a job in the latest free slot, not the earliest, is essential. Earliest-slot placement can block a later job with a tight deadline: with profits 10 and 9 and deadlines 2 and 1, earliest-slot placement puts the first job in slot 1 and loses the second (profit 10), while latest-slot placement keeps both (profit 19).

A coin system is canonical when largest-coin-first gives the fewest coins for every amount. Exhaustive checks up to amount 2000 give:

EDGE CASE. Without a coin of value 1, largest-first may find no answer when one exists. With coins $\{3, 5\}$ and amount 9, greedy takes 5, then 3, leaves 1 and is stuck, but $3+3+3$ works. The reliable method for any coin system is the dynamic program $c(a) = 1 + \min_{d \le a} c(a-d)$, which costs $O(ka)$ for $k$ denominations and amount $a$. That is pseudo-polynomial, as explained in Dynamic Programming Fundamentals.

Common misconceptions.