Greedy scheduling with an exchange proof

Prerequisites: Intervals, sorting, and proof by induction.

Learning objectives

• Prove earliest-finish interval scheduling.
• Distinguish maximum count from maximum value.
• Construct counterexamples to plausible greedy rules.

State the optimization problem exactly

Given half-open intervals [start,finish), choose the largest number of mutually nonoverlapping intervals on one resource. Touching endpoints are compatible: [1,3) and [3,5) can both be selected. Every interval has equal value in this version of the problem. The greedy algorithm sorts intervals by finishing time, takes the earliest-finishing available interval, then repeats among intervals starting at or after its finish.

Why finish time rather than start time or duration? A selected interval consumes the resource until its finish. Ending earliest leaves at least as much future room as any alternative first choice. This intuition needs a feasibility-preserving exchange argument to become a proof.

Exchange the first decision

Let g be an earliest-finishing interval and let o be the first interval in an optimal schedule. Replace o with g. Because finish(g)≤finish(o), every interval that followed o can still follow g. The replacement preserves the number of selected intervals and remains feasible. Therefore some optimum begins with g. Remove all incompatible intervals and apply the same argument to the remaining subproblem. This yields a proof by induction on the number of available intervals.

The proof does not say every locally attractive choice works. Choosing earliest start can select one long interval that blocks many short ones. Choosing shortest duration can select an interval in the middle that blocks two slightly longer compatible neighbors.

Trace and challenge the policy

For intervals A=[0,4), B=[1,2), C=[2,3), D=[3,5), E=[5,7), finishing order is B,C,A,D,E. Select B, then C. Skip A because it begins before C ends. Select D and E. Four intervals fit. Choosing A first would allow only A and E, giving two.

If intervals have values, maximizing count is no longer the objective. One long interval worth 100 can dominate several short intervals worth 1 each. Weighted interval scheduling instead admits a dynamic program: sort by finish time, find p(i), the last compatible earlier interval, and compare excluding i with value(i)+OPT(p(i)). The successful greedy proof relied on every selected interval contributing the same unit value.

Make tie and boundary behavior explicit

For equal finish times, a deterministic secondary ordering makes output reproducible. It need not change the maximum achievable count under the stated assumptions, but zero-length intervals and duplicate records need a clear contract. If switching resources incurs setup time, compatibility is no longer merely start≥previous finish. If several rooms exist, the state and objective change again.

The practical habit is to write the exchange before trusting the greedy rule. Identify what the replacement preserves, what it can only improve, and which assumption lets the subproblem retain the same form. Use MIT’s greedy and dynamic-programming materials to compare these proof structures, then produce your own counterexample when the objective changes.

Practice problem

Apply earliest-finish scheduling to A=[0,3), B=[1,2), C=[2,4), D=[3,5), E=[4,6), F=[6,7). Give the selected schedule and prove that no larger schedule is possible using the greedy exchange argument rather than enumerating all subsets. Then assign A value 100 and every other interval value 1; explain why the maximum-count schedule need not maximize total value.

Worked solution

Finishing order is B,A,C,D,E,F. Choose B, skip A, choose C, skip D, choose E, then F, giving four intervals. The exchange proof replaces the first interval in any optimal schedule with B without reducing its count, then repeats on intervals starting at 2; that recursion justifies the four-interval result. With A worth 100, schedule A,D,F has value 102, while B,C,E,F has value 4. Other value 102 schedules may exist, but the count-optimal result is plainly not value-optimal. The proof’s equal-contribution assumption has changed, so a weighted recurrence or another justified method is needed.

Check your understanding

Why can an optimal maximum-count interval schedule’s first interval be replaced by the earliest-finishing interval?

• The replacement necessarily has greater value.
• The replacement necessarily starts earlier.
• Any interval can replace any other without affecting feasibility.
• The replacement has no later finish and leaves every previously selected later interval feasible.

Explanation

The proof preserves count and all later start-time constraints; it does not require an earlier start or a higher weight.

A=[0,4) has value 100; B=[0,2) and C=[2,4) each have value 1. What changes when the objective becomes total value?

• No feasible schedule exists because endpoints touch.
• Selecting the shortest interval now always maximizes value.
• A is value-optimal, so the maximum-count greedy proof no longer solves the new objective.
• Earliest finish still proves B,C optimal because two is more than one.

Explanation

B,C has count 2 but value 2. A has value 100. Equal contribution per selected interval was essential to the original exchange objective.

Primary reading

• Introduction to Algorithms: lecture notes: MIT OpenCourseWare

Open the study and save your work →