Greedy choice: exchange proofs and counterexamples
Goal and prerequisite
Use sorting, asymptotic bounds and basic sets. A greedy algorithm commits to a locally preferred choice without revisiting it. To prove optimality, specify the objective, feasibility constraints, choice rule and why some optimal solution can include that choice. “It looks best now” is not a proof. Optimal substructure alone is insufficient; dynamic programming problems can have it without a valid greedy rule.
1. Unweighted interval scheduling
Each activity is a half-open interval [s,f), with s<f. Select as many nonoverlapping activities as possible on one resource. Activities touching at an endpoint are compatible. Sort by nondecreasing finish time. Scan in that order, accepting an activity whenever its start is at least the last accepted finish; initially no activity has been accepted. Arbitrary tie-breaking between equal finish times is allowed.
Example: A=[0,3), B=[1,2), C=[2,4), D=[3,5), E=[4,6). Finish order B,A,C,D,E. Accept B, reject A, accept C, reject D, accept E: three activities. The shortest duration rule or earliest start rule is a different algorithm.
2. Exchange proof, not just a trace
Let g be an activity finishing earliest. Let O be an optimal nonempty schedule, whose first activity is o. Since f(g)<=f(o), replace o by g. Every later activity in O starts at or after f(o), hence at or after f(g). Replacement preserves feasibility and the number selected. Therefore some optimum begins with g. The remaining activities must start at or after f(g); apply the same argument to this smaller residual instance. Induction proves the greedy schedule has maximum cardinality. Empty instances form the base case.
The exchange changed only the first choice and did not reduce the objective. This depends on equal value per activity. Sorting costs O(n log n), scanning O(n). With already finish-sorted input, the scan alone is O(n).
3. Counterexamples expose missing assumptions
Earliest-start fails: [0,10), [1,2), [2,3), [3,4). It takes only the first, while the last three are compatible. For weighted activity scheduling, earliest finish fails: [0,1) weight 1 and [0,2) weight 100 overlap. The rule takes value 1 instead of 100. Replacing an optimal activity with an earlier-finishing one can decrease value, so the cardinality exchange proof no longer works.
Coin-change greedy also depends on denominations. With unlimited coins {1,3,4} and amount 6, largest-first takes 4+1+1 (three coins), but 3+3 needs two. A familiar currency pattern is not proof for arbitrary denominations. The next DP lesson solves this exact counterexample systematically.
4. When density is provably safe
In fractional knapsack, each item may be split, weights are positive, values nonnegative, and value scales linearly with the fraction taken. Sort by value/weight and fill capacity in decreasing density. If a feasible solution takes some lower-density weight while higher-density weight remains available, exchanging equal amounts of weight cannot reduce value, and improves it if densities differ. Repeat to obtain a density-ordered optimum.
This argument fails for indivisible 0/1 items because an equal-weight fractional exchange may be illegal. With capacity 50 and items (weight,value)=(10,60),(20,100),(30,120), density-first 0/1 selection takes the first two for 160; the latter two give 220. Fractional selection takes the first two and 20/30 of the third for 240, which is valid only in the fractional model.
Proof checklist
Write the solution being exchanged, show feasibility after exchange, compare objective values, and identify the smaller remaining problem. A single counterexample refutes a universal greedy claim; many successful examples cannot prove one. This lesson covers the design principle, not a new catalogue of specialized greedy algorithms.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. For unweighted interval scheduling, the proved greedy choice is:
A. Earliest start B. Shortest duration C. Earliest finish D. Largest interval
Answer: C
A: A long early activity can block many.
B: Shortest duration is not the proved rule.
C: Exchange preserves the number and future feasibility.
D: Large intervals can block alternatives.
P02. Are [1,3) and [3,5) compatible under the stated convention?
A. Yes B. No C. Only with equal weights D. Only after shortening one
Answer: A
A: Half-open intervals may touch at endpoints.
B: They share no occupied time.
C: Weights do not decide overlap.
D: No change is necessary.
P03. Greedy largest-first for coins {1,3,4}, amount 6 uses how many coins?
A. 1 B. 2 C. 3 D. 6
Answer: C
A: There is no coin 6.
B: Two is optimal via 3+3, not this greedy trace.
C: Greedy selects 4+1+1.
D: It starts with 4 rather than all ones.
P04. Why does the unweighted exchange proof fail for weighted activities?
A. Sorting is impossible B. Replacement can reduce total value C. Endpoints cannot touch D. Weights change interval lengths
Answer: B
A: Finish-time sorting still works mechanically.
B: Equal cardinality does not imply equal value.
C: The interval convention can stay the same.
D: Weights need not affect time intervals.
P05. Capacity 50, items (10,60),(20,100),(30,120): optimal 0/1 value?
A. 160 B. 180 C. 220 D. 240
Answer: C
A: Density greedy first two is suboptimal.
B: First and third are feasible but worse.
C: Second and third weigh 50 and value 220.
D: 240 needs a fraction of the third item.
P06. A valid exchange proof must establish:
A. Only that the local choice is fast B. Feasibility and no worse objective after exchange C. That all optimal solutions are identical D. That every item is chosen
Answer: B
A: Speed does not prove optimality.
B: Both are necessary for replacing part of an optimum.
C: There can be multiple optimal solutions.
D: Feasibility may require excluding items.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in