Motivation
Suppose several requests want exclusive use of the same room, and the objective is to accept as many requests as possible. Taking the first request in the input is arbitrary. Taking the shortest request seems to save time. Taking the earliest-ending request seems to leave room for later work. Only the last of these rules has the correctness proof developed here.
A greedy algorithm commits to a choice without reconsidering it. Such a commitment needs a reason that some optimum can respect it. An exchange proof supplies that reason by modifying an optimal answer without making it worse. The remaining problem must then be described accurately enough to repeat the argument.
This example introduces those two obligations without claiming that every optimization problem admits a greedy rule. We will distinguish maximum cardinality from a schedule to which no further request can be added, and distinguish counting requests from maximizing their total value.
Definitions
Definition 8.1.1
(Positive-length half-open requests)
The input is a finite list of requests with distinct identities. Request occupies , where the endpoints are finite real numbers and . Endpoints may be negative. Two requests are compatible when their occupied sets are disjoint, equivalently when or . Thus one request may start exactly when another finishes.
A feasible schedule is a subset of pairwise compatible requests, listed in chronological order. Its consecutive requests satisfy finish at most next start. Its size is the number of accepted identities. Identical positive-length intervals with different identities still conflict.
A maximum schedule has largest possible size. A maximal schedule merely permits no additional request to be inserted while retaining feasibility. A greedy choice is safe for a residual problem if at least one maximum residual schedule can begin with that choice. Safety does not require every optimum to contain it.
For a current finish threshold , the residual list consists of requests whose starts are at least . Initially no request has been chosen, so there is no threshold. An implementation uses a separate flag for this state; initializing the threshold to zero would incorrectly exclude requests that end before time zero.
Theorem/proposition
Lemma 8.1.2
(Earliest finish is an exchangeable first choice)
For any nonempty residual list, let be a request of minimum finishing time, breaking ties arbitrarily. There is a maximum schedule for that list whose first request is . This remains true after a previously chosen feasible prefix, provided every residual start is at least the prefix's last finish.
Theorem 8.1.3
(Earliest-finish scanning maximizes the number accepted)
Sort all requests by nondecreasing finish, breaking ties arbitrarily. Scan once. Accept the first request; thereafter accept a request precisely when its start is at least the last accepted finish. For an empty input return the empty schedule.
The resulting schedule has maximum cardinality. Comparison sorting followed by scanning uses exact comparisons and indexed operations; a merge-sort implementation uses words including its working storage and the output.
Theorem 8.1.4
(The greedy schedule stays ahead)
Let be the greedy schedule, and any feasible schedule in chronological order. For every with , the greedy schedule contains and . Consequently . The theorem compares finishing times, not the identities of the accepted requests or their total occupied time.
Proof sketch or proof idea
Exchange the first request, without duplicating an identity
Proof
(Replacing the first request of an optimum)
Choose any maximum schedule from a nonempty residual list. Its size is at least one because any single request is feasible. By the definition of ,
If already occurs in this schedule, it must be first. Otherwise a preceding first request would satisfy
an impossibility. If is absent, replace by . For , the next request starts at least at the old first finish, and hence at least at . All later compatibility relations remain unchanged. For there is no suffix to check. The new schedule contains distinct identities and has the same maximum size.
After a fixed prefix, also starts at least at the last prefix finish, because it belongs to the residual list. The exchange therefore preserves the entire prefix. It asserts the existence of an optimum respecting the next choice, rather than claiming that the original optimum was unique.
Proof X-ray
What exactly survives the exchange?
The proof discharges three separate obligations, each with its own hypothesis. The inequality from minimum finish preserves every request after the replaced first request. Residual membership, not minimality, preserves compatibility with the fixed prefix. The chain that rules out a later occurrence of uses positive length at its strict step; without it, could sit later in the optimum and the replacement would count one identity twice. Saying merely that leaves more time checks only the first of the three.
Identify the smaller problem after making the choice
Proof
(Residual correspondence and induction)
Once is accepted, the remaining problem consists exactly of requests starting at least at . Any compatible suffix after lies in this list, and every feasible schedule from this list may be appended to . Write for maximum cardinality and for the current residual list. The exchange lemma and this correspondence give
The smaller list excludes itself because its length is positive. It contains fewer requests, so induction on the number of remaining requests proves repeated earliest-finish selection optimal. The empty list has optimum zero and supplies the base case.
This illustrates the proof pattern: first prove a safe choice, then prove the exact residual correspondence. Merely knowing that an optimum has an optimal suffix is insufficient; many problems have that property while a proposed greedy first step fails. Our shortest-duration counterexample below has precisely such a failed first step.
Margin Note
Try to break a greedy rule first
Before proving a greedy rule, try to defeat it with two or three intervals; each counterexample below needs at most five. A rule that survives small cases is a candidate for an exchange proof, not yet a theorem.
Explain why a single sorted scan implements that recursion
Proof
(The scan makes exactly the residual choice)
Accepted finishes strictly increase: the next accepted start is at least the current finish, and its own finish is strictly larger than its start. A request rejected for starting before the current finish will therefore never become eligible later. It can be discarded permanently.
At any step, a request eligible after the last accepted finish has its own finish strictly larger than that threshold. It cannot already have been selected. The first eligible request encountered in the sorted remainder has minimum finish among all eligible requests; earlier rejected entries cannot become eligible again. Thus the scan makes exactly the residual choice analyzed above. Arbitrary order among equal finishes is allowed by the exchange lemma.
A second proof: compare against every feasible schedule
Proof
(Stays ahead by induction on the competitor)
If the comparison schedule is nonempty, exists and , because has minimum finish in the entire input. Suppose exists and . If exists, feasibility gives
Thus is eligible after . Its positive length makes its finish strictly larger than , so it cannot be one of the already selected greedy requests. There is an eligible unselected request; the greedy process cannot stop yet. Its next minimum-finish choice finishes no later than . This proves both the existence and the inequality at each stage.
Induction through all comparison requests shows . Empty comparison schedules require no induction and satisfy the bound automatically.
The stays-ahead statement supplies a useful alternative invariant. It avoids a common incomplete argument that compares finishing times only while both schedules happen to exist, then silently assumes the greedy one cannot end first.
Concept lensAlgorithmic
A safe choice is stronger than a plausible local score
Finishing early is useful because an exchange preserves a whole optimal suffix. Short duration or early start alone provides no such suffix guarantee. Greedy correctness belongs to the combination of the objective, compatibility rule and exchange property; the score's intuitive appeal is not a substitute for them.
Count work under stated input conventions
Proof
(Cost of sorting and scanning)
Comparison merge sort repeatedly divides the list and merges sorted halves in linear work per level; there are logarithmically many levels. Scanning the sorted list performs one compatibility test per request and outputs at most identities. This proves the stated time and storage bounds, including constant work for an empty input. Already finish-sorted input needs only linear scanning work.
Finite real endpoints here use exact comparisons. If endpoints are integers of absolute value at most , endpoint comparisons and identity/index arithmetic can be charged by bits per operation in an indexed-array model with primitive address access. The operation count times this width is an arithmetic/index bit bound. No precision tolerance is introduced: replacing an exact endpoint comparison by an approximate test changes the compatibility problem.
Worked examples
Worked example 8.1.5
(Touching endpoints, negative times and tied finishes)
Use , , , , , , , . Their finish order is , with the tie reversible.
Accept , reject , accept , reject , accept , reject , accept and accept . The answer has five requests. If precedes in the tie, the answer also has five. Equality at the successive finish/start boundaries is allowed. Both schedules are maximum by the theorem. A threshold incorrectly initialized to zero would already lose .
Worked example 8.1.6
(Earliest start and shortest duration both fail)
For earliest start, take and four requests , , , . starts strictly first but blocks all four others. The singleton containing is maximal: none can be added. Its size one is smaller than the maximum size four.
For shortest duration, take , , . is uniquely shortest, with duration two, but overlaps both other requests. Choosing it first and removing conflicts yields one request. followed by yields two. Saving the most duration locally does not preserve an optimal suffix.
Worked example 8.1.7
(Counting requests is different from maximizing value)
Assign values one to and , and value ten to . Earliest finish accepts and , maximizing cardinality two but earning only two. The single earns ten. The exchange replacing by preserves the number one at that step but reduces the value, so it is not a value-preserving proof.
Nor does this mean one should always choose the most valuable request: give a long value ten and its three consecutive length-two subintervals value four each. The heaviest-first singleton earns ten, whereas the three short requests earn twelve. This note proves the unit-count objective; a weighted optimization method needs its own reasoning.
Common mistakes
Counterexample mode
Dropping positive length changes the model
If zero-length half-open intervals are allowed as empty occupied sets, is disjoint from . The pair is feasible under set-disjointness. Earliest finish selects first, then the threshold 1 rejects , whose start 0 is smaller, giving only one request instead of two. Positive length was used to order disjoint requests and to exclude previously chosen requests from the residual list. Our theorem explicitly assumes it.
The remaining errors keep the model but misread what the theorem says.
Common mistake
(Closed intervals with the half-open comparison)
Closed intervals have a different endpoint convention: and intersect. Under that model the compatibility test must be the strict or . Keeping the non-strict comparison while switching to closed intervals accepts conflicting pairs.
Common mistake
(Maximal is not maximum, and maximum is not unique)
A schedule to which nothing can be added may still be far from optimal: the singleton in the second worked example is maximal of size one, while the maximum is four. Conversely, optimal cardinality does not determine the output. The finish tie in the first worked example already gives two different optimal schedules.
Summary
Earliest finish is safe because exchanging it for an optimal first request preserves the full suffix and any fixed prefix. Exact residual correspondence then permits induction, and a sorted scan implements those choices efficiently. A stays-ahead proof independently establishes that the greedy schedule cannot run out before any competitor. The objective and endpoint hypotheses are essential.
Exercises
Quick check
(For , , , , list the greedy outputs for both orders of the finish tie. Explain why they have equal size and whether either output is the unique optimum.)
Bound every feasible schedule using the overlap of and .
Solution · Answer
is selected first, even though its times are negative. If precedes , select , reject and select , giving . If precedes , select , reject and select , giving . and overlap on , so any feasible schedule contains at most one of them; adding and gives the upper bound three. Both outputs attain it and differ, so uniqueness is false. Touching endpoints cause no conflict under the half-open convention.
Quick check
(A student says that choosing a request, deleting every conflict and repeating must be optimal because the result is maximal. Give a counterexample from the worked examples and state which exchange claim would be needed to repair this reasoning.)
Compare the size of a maximal schedule with the maximum.
Solution · Answer
Choosing first deletes the four compatible short requests inside it and returns a maximal singleton. The optimum contains all four shorts. To justify a greedy choice, one must prove that some maximum residual schedule contains that choice in the required first position, while keeping any chosen prefix feasible. Such an exchange is impossible for in this instance, because every schedule containing it has size one. Mere inability to add to the final answer does not compare it with answers obtained by replacing choices.
Quick check
(A feasible competitor has seven requests and the greedy procedure has already selected four, with . Prove that exists and . Explain the role of positive length.)
Show first that is eligible after .
Solution · Answer
The competitor's fifth start satisfies , so is eligible. Positive length makes , whereas every previously chosen greedy finish is at most . Thus is not already selected. The residual list is nonempty, so the greedy fifth request exists; minimum finish gives . Repeating this reasoning, rather than assuming equal schedule lengths, proves the general stays-ahead result.