A greedy algorithm builds a solution by making one locally best choice after another and never revising a choice. Many plausible greedy rules are wrong, so the useful skill is not designing a rule but proving it. The standard proof technique is the exchange argument: take any optimal solution, and show it can be modified, step by step, into one that agrees with the greedy choice without becoming worse. The cut property in the minimum-spanning-tree unit is one instance; this unit isolates the method and applies it to two other problems. Greedy algorithms and dynamic programming both rely on optimal substructure, but a greedy algorithm commits to a single subproblem instead of comparing several, and the exchange argument is what justifies that commitment.
1. The pattern
Definition 19.1.1
(Greedy-choice property and optimal substructure)
Suppose a problem asks for a feasible solution minimizing or maximizing an objective. A greedy algorithm picks an element by a fixed rule. To prove it correct, show two properties.
- Greedy-choice property. For every instance, some optimal solution contains the greedy choice.
- Optimal substructure. After the greedy choice is fixed, the remainder of an optimal solution containing it is an optimal solution of a smaller instance of the same kind.
Then induction on the size of the instance proves that the greedy algorithm is optimal: it makes a choice consistent with some optimum, solves the smaller instance optimally by the induction hypothesis, and the union is optimal. The heart of the work is property 1, and it is proved by exchange: let be an optimal solution not containing the greedy choice ; construct that contains and is at least as good as . A proof that merely shows the algorithm's output is feasible, or optimal on examples, is not a proof.
A second form is the adjacent-exchange argument for ordering problems: show that in any order, swapping two adjacent items that violate the greedy rule does not make the objective worse, and strictly improves it when the violation is strict.
2. Interval scheduling
Definition 19.1.2
(Compatible requests and interval scheduling)
Problem. Given requests, request occupying the half-open interval with , choose a largest set of pairwise compatible requests, meaning their intervals are disjoint. Half-open intervals mean that and are compatible.
Greedy rule (earliest finish time). Repeatedly choose, among the requests compatible with those already chosen, one with the smallest finishing time.
sort requests by f (ties broken arbitrarily)
last = -infinity; chosen = []
for each request i in this order:
if s_i >= last:
append i to chosen
last = f_i
return chosen
Because the requests are processed by increasing finish time, the chosen request is compatible with all earlier chosen requests exactly when the finish time of the most recently chosen one, which is the largest finish time so far.
Theorem 19.1.3
(Optimality of earliest finish time)
The algorithm returns a maximum-size set of compatible requests.
Proof
(Exchanging the first request)
Induction on the number of requests. For zero requests the claim is trivial. Let be the first request chosen, which has the minimum finish time over all requests (ties: any minimum).
Greedy-choice property. Let be an optimal set, with its intervals sorted by start (equivalently by finish, since they are disjoint): . Then because has the smallest finish time overall. If nothing changes. Otherwise define . Request ends no later than , which ends no later than starts, so is compatible with . Hence is compatible with , so it is optimal and contains .
Substructure. Let be the set of requests with , exactly those compatible with . Any compatible set containing is together with a compatible subset of . If were not a maximum compatible subset of , replacing it by a larger one would give a larger compatible set containing , contradicting the optimality of . So is optimal for .
The algorithm after choosing is exactly the algorithm run on , because it skips requests starting before and the remaining requests are in finish order. By induction it returns an optimal set for , and adding gives , the optimum.
Proof X-ray
Where the finish-time rule enters the exchange
The proof has one non-routine step: replacing by . Each fact it needs is used at a definite place. First, holds only because has the minimum finish time over all requests; this is the only place where the greedy rule is used. Second, the optimal intervals are pairwise disjoint, so ; chaining the two inequalities gives , and the same bound holds for because their starts are not earlier than . Third, the substructure step turns the exchanged optimum into an optimum of the smaller instance .
Remove the first fact and the exchange fails. For the earliest-start choice and , we have , so collides with . The argument closes because does not contain (as ), so has fewer requests than the original instance and the induction hypothesis applies.
Complexity. Sorting dominates: , and the scan is .
Counterexample mode
Earliest start and shortest request are not optimal
Claim: choosing the request that starts earliest, or the shortest request, always yields a maximum compatible set. Both claims are false. For , , the earliest-start rule picks , which overlaps both others, so it returns 1 request, while is compatible and has 2. For , , the lengths are , so the shortest-request rule picks ; it overlaps on and on , leaving 1 request, while and are compatible because and are disjoint. The repair is the finish-time rule: on the first instance it picks and then ; on the second it picks (finish 5), skips (start ) and picks (start ).
3. Worked example: interval scheduling
Worked example 19.1.4
(Earliest finish time on eight requests)
Requests (half-open): A , B , C , D , E , F , G , H . Sorted by finish: A (4), B (5), C (6), D (7), E (9), F (9), G (10), H (11).
- A: , choose; last .
- B: start , skip. C: start , skip.
- D: start , choose; last .
- E: start , skip. F: start , skip. G: start , skip.
- H: start , choose; last .
The result is , of size 3. By the theorem, no compatible set has four requests. For comparison, the earliest-start rule picks C first (start 0), then the first request starting at or after 6, namely G, then nothing starting at or after 10 (H starts at 8): two requests, strictly worse.
Worked example 19.1.5
(Touching intervals and tied finish times)
Take , , , . The finish times are , so and tie. With the order : choose (last ); skip (start ); choose (start , because and are disjoint); skip (start ). The result is . With the order the same steps give . The two outputs are different sets of the same size , as the theorem allows: it fixes the size of the answer, not the set. The tied choice never changes the later steps, because and have the same finish time .
4. Minimizing weighted completion time
Definition 19.1.6
(Completion time and weighted completion time)
Problem. jobs run one at a time on one machine without gaps, starting at time 0. Job has processing time and weight . In an order, the completion time of a job is the sum of the processing times of all jobs up to and including it. Minimize .
Greedy rule (Smith's rule). Process jobs in nondecreasing order of the ratio .
Lemma 19.1.7
(Adjacent exchange)
Suppose jobs and are adjacent in a schedule, immediately before , with the pair starting at time . Exchanging them changes the objective by exactly (cost before minus cost after), and no other job's completion time changes.
Proof
(Only the swapped pair changes)
Other jobs finish at the same times, because the block of the two jobs occupies the same interval either way. Before the swap, the pair contributes ; after, . Subtracting, the terms and and cancel, leaving .
Since , we have exactly when .
Theorem 19.1.8
(Smith's rule is optimal)
Every order by nondecreasing minimizes , and all such orders have the same cost.
Proof
(Removing adjacent inversions)
Let be an optimal order (one exists, because there are only finitely many orders). If it contains an adjacent pair with (a strict inversion), swapping them strictly reduces the cost by the lemma, contradicting optimality. So has no adjacent strict inversion, which means consecutive ratios are nondecreasing, so by transitivity the whole order is nondecreasing in ratio. Any two orders that are nondecreasing in ratio differ only by permuting jobs of equal ratio; swapping adjacent jobs of equal ratio changes the cost by by the lemma, and any permutation of equal-ratio blocks is a sequence of such swaps. So all nondecreasing orders have the cost of , which is the optimum.
Proof X-ray
Why local swaps give a global optimum
The lemma is purely local: it prices one adjacent swap. The step that makes it global is the choice of as an optimal order, which exists because there are finitely many orders. Strictness is where optimality is contradicted: a strict inversion gives a strictly positive saving , so could be improved. The positivity is used to turn the sign of into a comparison of ratios; with a zero weight the ratio would not capture the sign. Having no adjacent strict inversion makes the sequence of ratios nondecreasing, and then only equal-ratio blocks are free, where every swap saves exactly , so all such orders cost the same.
5. Worked example: Smith's rule
Worked example 19.1.9
(Smith's rule on three jobs)
Jobs: with , ratio ; with , ratio ; with , ratio . Smith's order is with completion times and cost .
Checking all six orders confirms it is optimal. : completions , cost . : , cost . : at 1, at 4, at 6: . : 14. : at 2, at 5, at 6: . : at 2, at 3, at 6: . The minimum is 14.
6. Common mistakes
Counterexample mode
Largest weight first is not optimal
Claim: processing jobs by nonincreasing weight minimizes . Take jobs and . Running first gives , and cost . Running first gives , and cost . So the weight-first order is not optimal. The ratios are and , and Smith's rule runs first, as the cost comparison requires. The repair is to use the ratio , not the weight alone.
Common mistake
(Feasible, or optimal on examples, is not a proof)
A greedy rule must be proved optimal for every instance. Showing that the output is feasible, or optimal on a few instances, establishes neither the greedy-choice property nor optimal substructure. The earliest-start and shortest-first rules above always produce feasible outputs and look natural, and both fail.
Common mistake
(An exchange that leaves the feasible region)
The exchange must start from an arbitrary optimal solution , not from the greedy solution, and the modified solution must be checked to be feasible. In interval scheduling, replacing by is feasible only because and the other intervals start after . A swap whose result is infeasible proves nothing.
Common mistake
(Direction of the ratio and ties in Smith's rule)
Smith's rule sorts by nondecreasing, equivalently by nonincreasing; the reverse direction puts long, light jobs first. Jobs with equal ratio may be placed in any order here, since swapping them changes the cost by . In other greedy problems ties can matter, so state what is claimed about them.
Exercises
Quick check
(Apply earliest-finish-time scheduling to , , , , , .)
Sort by finish time first.
Solution · Answer
Sorted by finish: (2), (3), (5), (7), (9), (10). Choose ; last . starts at , skip. starts at , choose; last . starts at , skip. starts at , choose; last . starts at , skip. The chosen set is with 3 requests.
Quick check
(Give a three-request instance on which earliest start first is not optimal.)
Let one request be very long.
Solution · Answer
Take , , . Earliest start picks , which overlaps both others, giving 1 request. The set is compatible and has 2 requests.
Exercise 19.1.10
(Order the jobs : , , , by Smith's rule and compute the cost. Show that the two valid tie orders give the same cost.)
Core
Solution(3)
- 1
Compute the ratios and sort
The ratios are , , , . A nondecreasing order is with ratio 1, then and with ratio 2 in either order, then .
- 2
Cost of the first tie order
Order has completion times , so
Because: The completion time is the running sum of processing times.
- 3
Cost of the other tie order and comparison
Order has completion times , so the cost is . Both tie orders cost 46.
Quick check
(Using Smith's rule, show that to minimize the sum of completion times of jobs with processing times one runs the shortest job first, and compute the minimum.)
All weights equal 1.
Solution · Answer
With all weights equal to 1, the ratio , so Smith's rule orders by nondecreasing processing time: . Completion times are , and the sum is . For comparison the order gives with sum .