They still fit: every later appointment starts at or after O finishes, and G finishes no later. The replacement preserves the appointment count. Thus at least one optimal schedule starts with the greedy choice.

After making the replacement, solve the remaining appointments beginning at or after G ends. Repeating the same argument justifies every commitment. The proof does not claim all optimal schedules are identical.

Intervals are half-open [start,end), with start < end. Therefore one interval ending at time 2 is compatible with another starting at 2.

def schedule(intervals):
    chosen = []
    finish = float("-inf")
    for start, end in sorted(intervals, key=lambda interval: interval[1]):
        if start >= finish:
            chosen.append((start, end))
            finish = end
    return chosen

assert schedule([(0, 10), (1, 2), (2, 3)]) == [(1, 2), (2, 3)]
assert schedule([(1, 2), (2, 3)]) == [(1, 2), (2, 3)]
assert schedule([]) == []

Sorting costs O(n log n) and the scan O(n). This Python implementation makes a sorted copy and returns up to n selected intervals, so total additional storage is O(n).

Why not earliest start? One early long interval can block several short ones. Why not shortest duration? (0,3), (3,6), (2,4) makes the shortest interval block two compatible longer ones. Finishing early is the specific property the exchange proof uses.

Recognition signal: can you transform an arbitrary optimum to contain your first choice without reducing its objective or breaking feasibility? An explicit transformation is stronger than “it leaves room.”

Analogy limit: leaving more time is sufficient here because all appointments have equal value and there is one resource. Other objectives and constraints can invalidate the exchange.

Not necessarily. The earlier-finishing appointment may pay less. The proof preserved count, not income, so it no longer establishes optimality.