Greedy exchange arguments
Prove when an irrevocable local choice can replace part of an optimum, and build counterexamples when the objective changes.
On this page
The question for today
What you’ll understand
- Use an exchange to preserve an optimal solution containing a greedy choice.
- Prove earliest-finish interval scheduling for maximum cardinality.
- Explain why the same rule fails for weighted objectives.
A greedy algorithm chooses something attractive now and commits without searching every possible future. The danger is that a locally appealing decision blocks a much better combination. An exchange argument answers that danger constructively: take an optimal solution that disagrees with the greedy choice and replace part of it without worsening its value. The proof identifies the exact structure that makes the local decision safe, and it reveals which changes to the problem destroy that safety.
State feasibility and the objective separately
For interval scheduling, each job has a start time strictly smaller than its finish time. Represent it as a half-open interval so that one job may begin exactly when another finishes. We want the largest number of pairwise nonoverlapping jobs on one resource. The greedy rule sorts by nondecreasing finish time, selects the earliest-finishing compatible job, and repeats on the remaining compatible jobs. Equal finish times can be broken arbitrarily because the argument uses a non-strict finish comparison.
Several plausible alternatives fail. The shortest job may lie in the middle and overlap two mutually compatible longer jobs. The earliest-starting job can occupy the resource almost all day. These failures matter because a greedy rule is not specified by the word greedy alone. Its ordering, compatibility test, and objective form a complete mathematical proposal. Sorting takes O(n log n) comparisons, followed by a linear scan when endpoints are directly comparable and jobs fit ordinary records.
Exchange one decision, then recurse on the remainder
Take a maximum-cardinality feasible schedule O and order its jobs by time. Let its first job be o₁ and the greedy first job be g. The greedy rule guarantees that g finishes no later than o₁. Replacing o₁ by g keeps the number of jobs unchanged, and every subsequent job still starts after g finishes. Thus at least one optimum agrees with the greedy first decision. The claim is existential: other optimal schedules may make different first choices.
Now restrict the instance to jobs starting after g finishes. If the remaining portion of the exchanged optimum were not optimal for this restricted instance, a larger remainder could replace it and improve the original optimum, a contradiction. This gives an induction on the number of remaining jobs. Notice both components: a safe first choice and an optimal residual problem. Merely showing that each chosen job is compatible proves feasibility, not maximum cardinality.
Change the objective and recheck the exchange
Suppose jobs carry rewards and the objective is total reward. Replacing an optimal schedule's first job with an earlier-finishing job may now lower its value. The compatibility part of the proof survives but the objective comparison fails. A single high-reward job can outweigh several low-reward jobs, so neither earliest finish nor maximum cardinality answers the weighted problem. Dynamic programming will keep both possibilities instead of committing to one unsupported exchange.
Greedy reasoning also differs between offline and online settings. Sorting assumes all intervals are known before decisions are made. An online scheduler that sees jobs only as they arrive cannot necessarily perform the same ordering or revise accepted work. Resource constraints, multiple machines, setup times, and uncertain durations each change the feasible exchanges. When adapting a proof, identify precisely which replacement is allowed and why it preserves the measured objective. A convincing picture for one example is useful intuition, but the exchange must work for an arbitrary optimum.
Work it through
An exchange improves the first finish time
Choose the maximum number of jobs from A = [0,4), B = [1,3), C = [3,5), and D = [5,7). All rewards are one.
Sort by finish time: B finishes at 3, A at 4, C at 5, and D at 7. Select B, then C because it starts at 3, then D because it starts at 5.
If a candidate optimum starts with A, replace A by B. The replacement ends earlier, so every later job remains compatible. In particular, it makes room for C without disturbing D.
The schedule B,C,D has three jobs. No schedule has four because A overlaps B, so including every job is impossible. The exhibited feasible schedule and this upper bound agree.
The optimum cardinality is three, achieved by B,C,D. The half-open endpoint convention is essential to the compatibility of B with C and C with D.
The living notebook
Explore the model
Interactive lab · cache
Inspect a local rule before claiming optimality
Pause and reset, then set both controls to cache capacity 2 and request stride 8. Predict a two-address cycle and only two cold misses among the initial sixteen requests; inspect the counts. For a fresh comparison, pause and reset, then set capacity 2 and stride 4. Predict a four-address cycle and sixteen misses. The LRU instrument implements a specific local eviction rule, not interval scheduling. Use the contrast to ask what exchange proof would be needed before calling any local rule globally optimal; it does not establish offline cache optimality.
- Hits / requests
- 0 / 16
- Hit rate
- 0%
- Address-stream period
- 16 addresses
A fully associative LRU cache starts empty and requests address (i·s) mod 16. Hits move an address to the newest position; misses evict the oldest when full. Playback starts with 16 requests and adds two per second, capped at 4096 explicitly simulated requests. This toy stream is not a processor-cache benchmark. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forA precisely defined local rule can be inspected, but an optimum claim still requires a problem-specific proof.
Pause & reason
Check your understanding
Your turn
Try it yourself
Give rewards 1,1,1 to jobs [0,2), [2,4), [4,6), and reward 10 to [0,6). Compare earliest-finish scheduling with maximum total reward, and locate the failed step of the exchange proof.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Calculate the sum of the three short rewards before replacing the first job of the high-reward schedule.
Compare with the solution
Earliest finish chooses the three short jobs and earns three. The single job [0,6) earns ten, so it is the unique reward-maximizing choice in this instance. Replacing that long job with [0,2) preserves compatibility with any subsequent jobs, but drops its contribution from ten to one. The cardinality-preserving exchange no longer preserves reward. The feasible-schedule structure is unchanged; it is the objective comparison that fails, so the unweighted proof cannot justify the weighted algorithm.
Keep the idea
Take it with you
- A greedy proof exchanges an arbitrary optimum into one containing the chosen decision.
- Earliest finish is optimal for the number of nonoverlapping intervals on one resource.
- Rewards or online information can invalidate the same exchange even when feasibility is unchanged.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.