Proving Greedy Correctness (Exchange Argument) vs Recognizing It Fails
What This Concept Is
A greedy rule commits to a local choice. To establish exact optimality, show that some optimum contains that choice and that the remaining instance keeps the required structure. An exchange argument transforms an optimum to agree with the greedy decision without harming feasibility or objective. A staying-ahead proof is related but organizes the comparison through prefix inequalities.
Failing to find a proof is not proof of failure. One valid counterexample, however, disproves a universal exactness claim. Greedy methods can also be heuristics or proven approximations; these are different output guarantees.
Why It Matters Here
The same input shape can have different objectives. Earliest-finish interval selection solves maximum cardinality, but not arbitrary weighted profit. The weighted version becomes a central DP lab and capstone, so the boundary between the two algorithms must be explicit.
Concrete Examples
Maximum number of intervals. Intervals are half-open [s,f) with s<f,
and touching endpoints are compatible. Sort by finish and select the first
compatible interval repeatedly. Let g be the earliest-finishing interval and
o the first interval of an optimal schedule. Since finish(g)<=finish(o),
replacing o with g preserves every later interval and cardinality. The residual
problem contains intervals starting after g finishes; repeat the argument.
Sorting takes O(n log(n+1)); the scan takes O(n).
Weighted failure and repair. Jobs (start,finish,value) are
[(0,2,3),(2,4,3),(0,4,7)]. Earliest finish picks the first two for 6,
but the long job gives 7. Sort by finish and define p(i) as the number of
earlier jobs finishing no later than job i starts. For a 1-based prefix table:
D(i)=max(D(i-1), value[i-1]+D(p(i-1))), D(0)=0.
Take/skip partitions by identity. Binary search computes p in O(log n) per
job; tabulation and reconstruction take O(n) after sorting. Signed values
are allowed if an empty schedule is allowed.
Ratio-first knapsack failure. Items (2,3),(3,4), capacity 4. Ratio-first
takes (2,3) and cannot fit the other; value 3 loses to value 4. Fractional
knapsack has different feasible objects and a different exchange argument.
Common Confusion / Misconceptions
The matroid characterization concerns a specific hereditary independence system and weight-sorted greedy for every weight assignment. It does not say every correct greedy algorithm requires its feasible sets to form a matroid. Nor does a counterexample to one greedy rule prove that DP is the only option. Claims about approximation need a stated objective, assumptions and error bound.
How To Use It
State the local rule and the exact objective. Construct a swap in an arbitrary optimum and check all constraints, not merely the local cost. If the swap fails, look for a small separating instance. For weighted scheduling, explain why the prefix predecessor summarizes compatibility and why an additional budget would require extra state. Return original job IDs in chronological order.
Check Yourself
What property makes the earliest-finish swap safe? Why does replacing a weighted job lose the proof? Can a greedy algorithm be useful without being exactly optimal?
Mini Drill or Application
Change the long job's value in the three-job example from 7 to 6 and then 5. Feedback: at 6 both schedules are optimal; at 5 the pair is uniquely better in value. Tests must accept both witnesses in the tied case.
Read This Only If Stuck
CLRS: activity-selection exchange arguments and the greedy-choice property. Derive weighted scheduling separately rather than assuming the greedy proof transfers.