Data Structures & Algorithms / Optimization proofs and maintained aggregates / Lesson 14

Greedy exchange arguments and counterexamples

Prove a local choice preserves an optimum and recognize when changing the objective destroys that proof.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

A plausible local rule is only a hypothesis
Exchange the first interval of an optimum
Construct a counterexample by exposing opportunity cost

A plausible local rule is only a hypothesis

A greedy algorithm commits to a choice without exploring every later consequence. Correctness requires a structural argument that some optimal solution can be transformed to include that choice. For maximum-cardinality nonoverlapping intervals, earliest finishing time has such an exchange argument. Earliest starting time, shortest duration, or largest immediate reward need not solve the same problem. Define half-open intervals with start<finish, allowing one interval to begin exactly when another ends. Weighted reward, setup gaps, multiple resources, or zero-duration events change the contract and can invalidate the original proof.

Exchange the first interval of an optimum

Let g be an interval finishing no later than any other candidate. Take an optimal schedule and compare its first interval o. Replacing o with g cannot delay the next selected interval because g finishes no later than o. Thus an optimum exists containing g. The remaining intervals compatible with g form the same kind of problem, allowing induction. The first program implements that choice after sorting by finish time. The proof depends on maximizing count and the stated compatibility rule, not merely on having a sorted list or a short loop.

python Self-contained Python3 algorithm example using synthetic local data.

def schedule(intervals):
    if any(start >= finish for start, finish in intervals):
        raise ValueError("Intervals must have positive duration")
    selected = []
    last_finish = None
    for start, finish in sorted(intervals, key=lambda item: (item[1], item[0])):
        if last_finish is None or start >= last_finish:
            selected.append((start, finish))
            last_finish = finish
    return selected

print(schedule([(0, 3), (1, 2), (2, 4), (3, 5), (4, 6)]))
print(schedule([]))

Expected output

[(1, 2), (2, 4), (4, 6)]
[]

Touching endpoints are compatible. Sorting and selection produce one optimum, not every optimal schedule.

Construct a counterexample by exposing opportunity cost

For earliest-start selection, a long interval beginning first can block many short later intervals. For shortest-duration selection, a small middle interval can block two compatible intervals on its sides. A useful counterexample isolates the claimed rule and compares it with a clearly better feasible solution. Do not treat a failed alternative as proof that your preferred rule is correct; it only disproves that alternative. The exchange argument must still connect every accepted input to an optimum. Counterexamples are tools for refining the contract, not a replacement for a positive correctness proof.

Changing count to reward changes the optimization problem

The second program exhaustively evaluates a tiny weighted fixture. An earliest-finish choice takes the first reward4 interval and then the second reward4 interval, totaling8. A single compatible alternative interval has reward10 and is better. The unweighted greedy theorem does not apply to total reward. Weighted interval scheduling can instead use dynamic programming with a predecessor relation over finish order. The enumeration here is deliberately exponential and bounded to three intervals, serving as a transparent reference rather than a proposed production algorithm for large schedules.

python Self-contained Python3 algorithm example using synthetic local data.

from itertools import combinations

def best_reward(intervals):
    optimum = 0
    for count in range(len(intervals) + 1):
        for subset in combinations(intervals, count):
            ordered = sorted(subset, key=lambda item: item[0])
            if all(ordered[i - 1][1] <= ordered[i][0] for i in range(1, count)):
                optimum = max(optimum, sum(item[2] for item in subset))
    return optimum

intervals = [(0, 2, 4), (2, 4, 4), (0, 4, 10)]
print(best_reward(intervals))
print(sum(item[2] for item in intervals[:2]))

Expected output

10
8

A valid two-interval schedule loses to one higher-reward interval, proving count optimality is not reward optimality.

Include representation and output in the analysis

Sorting n intervals costs O(n log n) comparisons under the chosen model, and the greedy scan is linear. The returned schedule can contain O(n) intervals; sorting also requires its implementation-specific working storage. If input already arrives in valid finish order, that preparation can be avoided under an explicit precondition. Do not silently assume ordered input because one fixture happens to be ordered. Tie-breaking by start makes the example reproducible, but ties can still admit several equally large schedules. Validate feasibility and objective value rather than demanding one arbitrary optimum unless the tie policy is itself promised.

Use exhaustive tiny instances to challenge the theorem

Enumerate subsets of a small interval collection and compare the best compatible count with the greedy count. Include touching endpoints, nested intervals, equal finishes, disjoint intervals, and input permutations. Independently check that every returned interval came from the input and no pair overlaps under half-open semantics. Reject zero or negative duration under this lesson’s contract. Finite enumeration can catch an incorrect implementation or a mistaken assumption, while the exchange proof establishes why earliest finish generalizes. Keep the enumeration bounded and local rather than turning a teaching check into a large combinatorial load.

Common errors and fixes

Earliest-start scheduling is assumed optimal

Why it happens: A local preference was accepted without an exchange argument.
How to fix it: Use the proved earliest-finish rule for this count contract.
Prevent it next time: Test one long early interval against several short later ones.

Touching intervals are rejected as overlapping

Why it happens: Closed-end semantics were mixed with half-open intervals.
How to fix it: Use start>=last_finish for the declared contract.
Prevent it next time: Test [0,2) followed by [2,4).

Count-optimal greedy is reused for weighted reward

Why it happens: The objective changed while the proof was left unchanged.
How to fix it: Derive a weighted method such as an appropriate dynamic program.
Prevent it next time: Include a high-reward interval competing with two low rewards.

Check your understanding

1. What does replacing o with g preserve in the exchange proof?

Show worked solution

It preserves the number of selected intervals and cannot delay any later interval because g ends no later than o. Thus feasibility and objective count remain intact. The proof does not preserve arbitrary rewards, explaining why weighted scheduling needs another argument.

2. Why should tests accept different optimal schedules with the same count?