The data set
The explorer uses a different six-job data set from the three-interval table in Greedy choices and dynamic programming. Its jobs are ordered by finishing time, and each occupies a half-open interval: an earlier job ending exactly when the next begins is compatible. Change the reward of job E and watch the table, rather than carrying the earlier example's values into this one.
The predecessor index and the recurrence
Definition 2.5.1
(Predecessor index and prefix optimum)
List jobs by nondecreasing finish time . Job occupies the half-open interval with and carries a reward . Two jobs are compatible when their intervals are disjoint, so a job that ends exactly when another begins is compatible with it. The predecessor index is the largest with , and if there is none. Let be the maximum total reward of a compatible subset of jobs , with .
For job , is an index: it names a prefix of eligible jobs, not a reward and not a promise to choose that last job. When E starts at time 5, C ends at 5, so . The subproblem considers compatible subsets of A, B and C and selects one of maximum reward.
Theorem 2.5.2
(Weighted interval recurrence)
For ,
Moreover, among jobs , those compatible with job are exactly jobs .
Proof
(Include or exclude the last job)
For the intervals of and are disjoint exactly when : the other possibility would give . If then , and if then by the choice of . So the jobs among compatible with are exactly .
Now take an optimal compatible subset of . If , then is a compatible subset of , so its reward is at most , and an optimal subset of attains that value. If , then is a compatible subset of , so the reward of is at most ; conversely, an optimal subset of together with is compatible and attains that value. Every compatible subset falls into one of the two cases and both values are attained, so is their maximum. Induction on , with base , covers all rows.
Proof X-ray
Why one index stands for a whole set of jobs
The one non-obvious point is that the compatible earlier jobs form a prefix, so the include branch refers to a single smaller subproblem, . This is where the finish-time order is used: it makes the condition monotone in . Positive length, , is used to exclude the case . The split on whether is exhaustive and loses nothing, so no exchange argument is needed. The induction closes because both branches refer to strictly shorter prefixes, with as the base. A tie between the two branches does not affect the value, only which schedule the reconstruction returns.
The sort order is therefore part of the method and not a convenience.
Counterexample mode
Sorting by start time breaks the prefix
Claim: the jobs compatible with job among the earlier jobs always form a prefix , whatever order the jobs are listed in. List with reward , with reward and with reward by start time. The largest with is , so the formula would use the prefix , whose best reward is (take ). It would then report for a schedule containing both and , but these overlap, and the true optimum is . The repair is to sort by finish time, which makes monotone in and the compatible jobs a prefix.
Reading the trace
Worked example 2.5.3
(The default reward: E is taken)
Take . The predecessor indices of A through F are : for instance D starts at exactly when B ends, which is allowed, and F starts at exactly when D ends. The table is . Row 3 compares with ; row 4 compares with ; row 5 compares with ; row 6 compares with . Reconstruction skips row 6 because , takes E at row 5 and jumps to , skips row 3, takes B at row 2 and jumps to . The schedule has reward . The comparison at E considers whole schedules in the relevant prefixes, not just E against one neighboring job.
Worked example 2.5.4
(Reward 4: a tie that does not decide the schedule)
Set . Row 5 compares with : both alternatives equal , and the trace skips E on a tie. Row 6 then compares with and includes F, so the table is . Reconstruction takes F and jumps to , takes D at row 4 () and jumps to , and takes B. The schedule has reward . Choosing E at row 5 would also be optimal for that prefix, through with reward , but F overlaps E, so that prefix schedule cannot be extended to the full optimum. A tie in an intermediate row is not by itself a final schedule.
Worked example 2.5.5
(No predecessor and a zero reward)
Row 2 has , because no earlier job ends by time . The include branch is , which beats the exclude branch ; the base value is what lets this case need no special treatment. Now set . Row 5 compares with and skips E, and the remaining rows are as for reward , giving with reward . A zero-reward job is never taken: its include value cannot exceed , because is nondecreasing, and the trace takes a job only when including it is strictly better.
During reconstruction, selecting a job moves to its predecessor; skipping moves back one row. The value remains optimal for the remaining prefix in either case.
Common mistakes
Common mistake
(Reading the predecessor index as a chosen job)
The index marks a prefix of eligible jobs; it does not say that job is selected. For E, makes A, B and C eligible, but the best schedule inside that prefix has reward and consists of B alone, without C.
Common mistake
(Using the wrong endpoint comparison)
The data are half-open intervals, so the predecessor test is . If shared endpoints were treated as a conflict, the test would become , and the table would change. D starts at exactly when B ends. With the half-open rule and (jobs B and D), whereas with the strict rule , because only A ends before time , and .
Exercises
Quick check
(With E's reward at 9, which jobs does the reconstruction select, and what is their total reward?)
Start at row 6 and take a job only when including it is strictly better.
Solution · Answer
Row 6 compares with and skips F. Row 5 compares with , takes E and jumps to row 3. Row 3 compares with and skips C. Row 2 compares with , takes B and jumps to row 0. The selected jobs are B and E, with total reward .
Quick check
(What is , and why is it rather than ?)
Compare F's start time with the finishing times of D and E.
Solution · Answer
F starts at . Job D occupies and ends at , which is compatible under the half-open convention, so . Job E occupies and ends at , so it overlaps F and is not eligible. Hence .
Quick check
(What is the smallest integer reward of E for which the reconstruction selects E?)
Compare the include and exclude values in rows 5 and 6 as a function of .
Solution · Answer
Row 5 gives . At row 6, F is included when , and then E is not selected, because F overlaps E. For we get , so F is taken. For we get , a tie at row 6, so F is skipped; row 5 then takes E because . For larger rewards the same happens. The smallest reward is .