Weighted interval scheduling: the subproblem must exclude conflicts
Choosing the earliest-finishing activity maximizes the number of compatible activities in the unweighted problem, but it need not maximize total reward. Dynamic programming works once we identify the smaller problem that remains after choosing an activity.
1. Specify the scheduling model
There are n activities. Activity i occupies the half-open interval [s_i,f_i) with s_i<f_i and has reward w_i. Rewards are additive, and selecting nothing yields reward zero. The input is sorted by finish time, which makes every compatible prefix identifiable.
Definition 7.1.1
(Weighted interval scheduling and the predecessor index)
Two activities are compatible if their occupied intervals do not overlap; finishing exactly when another starts is allowed. The problem asks for a set of pairwise compatible activities of maximum total reward, where the empty set has reward . Sort the activities by nondecreasing finish time, breaking ties deterministically, and number them in that order.
- The predecessor index is the largest index with , or if no such index exists.
- is the greatest total reward of a compatible set chosen from the first activities, with .
Theorem 7.1.2
(Predecessor recurrence)
Let the activities be indexed in nondecreasing finish order, with and arbitrary real rewards . Then for ,
Proof
(Exclude activity i or include it)
Let be the family of compatible subsets of , the empty set included, so is the maximum of the total reward over . Split by whether is chosen.
Sets not containing are exactly the members of , so their best reward is .
Now take . By the sorting, , and , so : activity cannot start at or after . Hence is compatible with exactly when it finishes at or before , that is, when . The set is the prefix . Indeed, if then , and if then because is the largest index with that property.
Consequently a set containing is compatible if and only if it has the form with . Its reward is , so the best such reward is , and this value is attained. Every set in falls in exactly one of the two cases, and both bounds are attained, so is the larger of the two values. Negative rewards cause no trouble: the empty set belongs to and to , so neither branch is forced to take a loss.
The recurrence reads the table only at positions and , so the table can be filled for in order. Sorting alone does not solve the problem; its role is to make the compatible activities form a prefix.
Proof X-ray
Where each assumption enters the recurrence
The argument has one structural move: schedules that contain are in bijection with schedules of the prefix , by adding or removing . Three assumptions make that bijection legitimate.
First, sorting by finish time gives for every . Second, positive length gives . Together they rule out the only way an earlier index could be compatible with from the right, namely starting at or after , so compatibility with reduces to the single test . Third, because finish times are nondecreasing, that test cuts the indices below into a prefix, which is why one number summarizes every conflict.
The step then closes: the removed set is itself an arbitrary compatible set inside the prefix, so is exactly the quantity needed, and the maximum over two exhaustive cases is the maximum of the two case values. Remove the sorting hypothesis and the first and third points fail; the counterexample in the last section shows the recurrence returning a wrong value.
Concept lensStructural
The recurrence as a longest path
Take nodes and two kinds of edges into each node : an edge of weight (skip activity ) and an edge of weight (take it). Every edge goes forward, so the graph is acyclic and nodes can be processed in increasing order. The longest-path distance from node satisfies and , which is the recurrence for . A path from to corresponds to the set of activities whose take edges it uses: if it takes and later takes , it reaches node first, so and the two are compatible. Conversely, every compatible set gives such a path. Reconstruction is then the usual walk back along the edge that achieved each maximum.
2. Worked examples
Worked example 7.1.3
(Five activities with a boundary tie)
Activities below are already in finish order. Calculate each predecessor by comparing a previous finish to the current start, including equality.
i | interval | reward | p(i) | OPT(i) |
|---|---|---|---|---|
| 1 | [1,3) | 5 | 0 | 5 |
| 2 | [2,5) | 6 | 0 | 6 |
| 3 | [4,6) | 5 | 1 | 10 |
| 4 | [6,7) | 4 | 3 | 14 |
| 5 | [5,8) | 11 | 2 | 17 |
For example, activity 4 may follow activity 3 because 6 <= 6. At activity 5, exclusion gives 14 while inclusion gives 11+OPT(2)=17, so choose 5 and continue at index 2. At 2, inclusion gives 6 and exclusion gives 5, so choose 2. The selected intervals [2,5) and [5,8) have total reward 17. The predecessor is an index, not the total reward of a previous activity.
To reconstruct a schedule, start at i=n. If w_i+OPT(p(i)) > OPT(i-1), choose i and set i=p(i); otherwise set i=i-1. On a tie this policy skips i, yielding one valid optimum; choosing it on equality is also valid if reconstruction then continues at p(i). Reverse the selected indices at the end if chronological order is desired.
Worked example 7.1.4
(Negative rewards and the empty schedule)
Take the finish-sorted activities [0,2) with reward , [1,3) with reward and [3,5) with reward . Predecessors: activity 1 has p(1)=0; activity 2 starts at 1 but activity 1 finishes at 2, so p(2)=0; activity 3 starts at 3 and activity 2 finishes at 3, so p(3)=2.
Values: OPT(1)=max{0, -4+0}=0, OPT(2)=max{0, 2+0}=2, OPT(3)=max{2, -1+OPT(2)}=max{2,1}=2. Reconstruction: at 3, -1+2=1 is not larger than OPT(2)=2, so skip to 2; at 2, 2+0=2>OPT(1)=0, so choose 2 and jump to 0. The optimum is the single activity [1,3) with reward 2. Had every reward been negative, every inclusion test would fail and the reconstruction would return the empty schedule with reward 0, which is the boundary case OPT(0)=0 at work.
Worked example 7.1.5
(Computing p(i) by binary search)
Use the finish times 3,5,6,7,8 of the first example and compute p(5), where s_5=5. We look for the largest j in 0..4 with f_j <= 5, treating j=0 as always acceptable. Keep an interval [lo,hi] known to contain the answer, starting at lo=0, hi=4; while lo<hi, probe mid=ceil((lo+hi)/2) and set lo=mid if f_mid <= s_i, otherwise hi=mid-1.
Probe mid=2: f_2=5<=5, so lo=2. Probe mid=3: f_3=6>5, so hi=2. The interval is [2,2], so p(5)=2, matching the table. The two extreme cases need no or little probing: for i=1 the interval is [0,0] and p(1)=0 at once, and for i=2 (s_2=2) the probe mid=1 gives f_1=3>2, so hi=0 and p(2)=0. Each predecessor costs about log2 i probes.
3. Cost and a boundary trap
Sorting costs O(n log n). Since the finish times are sorted, binary-search the prefix 1,...,i-1 for the rightmost finish at most s_i, giving O(log n) per predecessor and O(n log n) total. Filling the table and reconstruction each take O(n), and the table, predecessor array and output use O(n) space. These claims assume constant-time comparisons and arithmetic on the supplied values. Scanning backwards for each predecessor is also correct but can cost Theta(n^2).
If intervals instead conflict when one endpoint equals the other, the compatibility test becomes f_j < s_i; the predecessor array and answer may change. The recurrence must match the problem's rules rather than an unstated convention.
Common mistake
(Using a strict inequality when touching endpoints are allowed)
Writing f_j < s_i while the model allows [a,b) and [b,c) together shortens the prefix. In the first worked example it gives p(4)=2 instead of 3, since f_3=6 is no longer accepted; then OPT(4)=max{10, 4+6}=10 instead of 14, and p(5) becomes 1 and the final answer drops from 17 to 16. Choose the test from the stated compatibility rule.
Common mistake
(Taking i-1 as the predecessor)
Sorting makes activity i-1 finish no later than i, but it may still overlap i. In the first example [6,7) (activity 4) overlaps [5,8) (activity 5), so w_5+OPT(4)=25 is not the value of any schedule. The correct predecessor is p(5)=2, which skips every activity that conflicts with activity 5.
The table also depends on the order of the input, as the next example shows.
Counterexample mode
The recurrence needs finish-sorted input
Suppose the activities are listed in the order activity 1 [2,4) with reward 5, then activity 2 [0,1) with reward 3, so the finish times 4 and 1 are not nondecreasing. Using the same definition, p(2) is the largest j<2 with f_j<=0; since f_1=4, we get p(2)=0. Then OPT(1)=5 and OPT(2)=max{5, 3+OPT(0)}=5. But the intervals [0,1) and [2,4) are disjoint, so the true optimum is 5+3=8. Activity 1 is compatible with activity 2 but lies after it in time, and the test f_j<=s_i only detects activities that finish before activity i starts. Sorting by finish gives [0,1) first and [2,4) second, so that p(2)=1, and the recurrence returns max{3, 5+3}=8.
Quick check
(Activities sorted by finish are [0,4) with reward 2, [3,5) with reward 3 and [4,7) with reward 1. Compute p(1),p(2),p(3) and OPT(1),OPT(2),OPT(3).)
Compare each finish with the start of the current activity, allowing equality.
Solution · Answer
p(1)=0. For activity 2 (start 3), f_1=4>3, so p(2)=0. For activity 3 (start 4), f_2=5>4 but f_1=4<=4, so p(3)=1. Then OPT(1)=2, OPT(2)=max{2, 3+0}=3, and OPT(3)=max{3, 1+OPT(1)}=max{3,3}=3. The tie shows two optimal schedules, {2} and {1,3}, both with reward 3.
Practice: overlapping activities
Quick check
(Consider activities [1,3) with reward 4, [3,4) with reward 4, and [2,5) with reward 9. Find the best reward and explain why choosing the earliest finish repeatedly is insufficient for weighted rewards.)
List which pairs are compatible before comparing totals.
Solution · Answer
In finish order, the first two are compatible and total 8. The third overlaps each of them and gives 9 alone, so the optimum is 9. Earliest-finish selection picks the first two and gets 8; that greedy rule optimizes a different objective, the number of activities, not necessarily total reward.
Practice: five finish-sorted activities
Quick check
(The finish-sorted activities are [0,2) reward 3, [1,3) reward 5, [2,4) reward 4, [3,5) reward 4, and [4,6) reward 3. Compute p, the DP values and one optimal schedule.)
Compute p first, then fill the table from left to right.
Solution · Answer
The predecessor array is [0,0,1,2,3]. Starting from OPT(0)=0, the values are 3,5,7,9,10: for instance, the fifth activity gives 3+OPT(3)=10, exceeding OPT(4)=9. Choose 5, then 3 because 4+OPT(1)=7>OPT(2)=5, then 1. The intervals [0,2), [2,4), [4,6) meet only at endpoints and total 3+4+3=10. This reconstruction follows the same inclusion/exclusion alternatives used in the proof.