When a greedy choice preserves the optimum

A room receives requests with fixed start and finish times. The objective is to accept as many requests as possible. Assume finitely many positive-duration intervals on one resource, with a request allowed to start exactly when another finishes. MIT’s interval-scheduling notes use this compatibility convention.

The greedy rule repeatedly takes an earliest-finishing available interval and retains only requests starting at or after its finish. Finishing early suggests leaving room for later work; the exchange argument supplies the guarantee that intuition alone cannot.

Let g be an earliest-finishing request and let o be the first request in an optimal schedule. Since finish(g) ≤ finish(o), replacing o with g leaves every later request feasible. The replacement preserves the number selected. Thus at least one optimal schedule begins with g, even if the original optimum did not.

The remaining requests form the same kind of problem after finish(g). The optimal schedule’s remainder must be optimal there: a larger feasible remainder would improve the whole schedule. Induction, starting from an empty set, repeats the exchange until no requests remain. The argument covers every finite input satisfying the stated conditions.

Now change the objective to total weight. In our constructed example, A occupies [0,2] with weight 1, B occupies [2,4] with weight 1, and C occupies [0,4] with weight 3. Endpoint touching is allowed, so A and B are compatible. Earliest finish selects A then B: two requests, total weight 2. Selecting C alone gives weight 3.

A plus B is optimal for cardinality, while C is optimal for weight in this example. The exchange preserves one request for one request, but need not preserve value. This example refutes the weighted guarantee; the general exchange proof establishes the unweighted guarantee.

When the objective changes, revisit what each proof step preserves. A convincing greedy explanation identifies the feasible replacement, the preserved objective and the smaller problem to which the argument applies again.