Weighted Interval Scheduling: take job j or skip it

The idea: weights break the greedy

Each job runs from a start time s to a finish time f and has a weight w (money, priority). Two jobs are compatible when one ends at or before the other starts. The goal is a set of compatible jobs with the largest total weight. Without weights, "take the job that ends first" is optimal (see Interval Scheduling). With weights, every simple greedy rule fails, and a one-row dynamic programming table solves it.

Earliest finish takes the light job F because it ends before D, and then D no longer fits. Heaviest first takes A (w9), which overlaps every other job. (Demo: greedy by earliest finish fails, Demo: greedy by heaviest job fails.)

Sort by finish time, then p(j)

Sort the jobs by finish time and number them 1..n. For job j define p(j) as the last job, in this order, that finishes by the time job j starts (0 if there is none). Because of the sort, jobs 1..p(j) all end by s[j], and jobs p(j)+1 .. j−1 all overlap job j: each of them ends after s[j] but no later than f[j]. The canvas colours them green and red.

Finding p(j) by binary search

The finish times f[1..n] are sorted, so p(j) is the last index with f[i] ≤ s[j]. A binary search finds it in O(log n) probes: look at the middle of the range; if it ends by s[j], keep it and search right for a later one, otherwise search left. On the canvas the range is blue and the probe is orange. A plain scan from j−1 down also works but costs O(n) per job.

lo = 1, hi = j-1, p = 0
while lo <= hi:
    mid = (lo + hi) / 2
    if f[mid] <= s[j]:  p = mid, lo = mid + 1
    else:               hi = mid - 1

The recurrence: take job j or skip it

Let OPT[j] be the best total weight using only jobs 1..j. For job j there are two choices:

• Skip it: the best is still OPT[j−1].
• Take it: jobs p(j)+1 .. j−1 overlap it and drop out, so add w[j] to the best of jobs 1..p(j).

OPT[0] = 0
OPT[j] = max( OPT[j-1],  w[j] + OPT[p(j)] )

It is the same skip-or-take shape as House Robber, but the "take" arrow jumps back to p(j) instead of always two cells. For the six jobs, p = 0, 0, 1, 0, 3, 3 and OPT = 0, 4, 4, 8, 9, 10, 14 (Demo: 6 jobs).

Which jobs? The trace back

Walk back from OPT[n]. If OPT[j] = OPT[j−1], job j was skipped: go to j−1. Otherwise it was taken: go to p(j). For the six jobs: OPT[6] = 14 ≠ 10, take job 6 (D) and go to p(6) = 3; OPT[3] = 8 ≠ 4, take job 3 (B) and go to 1; OPT[1] = 4 ≠ 0, take job 1 (C). Total 4 + 4 + 6 = 14.

Time, and when greedy is enough

Part	Cost
Sort by finish time	O(n log n)
p(j) for every job, binary search	O(n log n)
Fill OPT[1..n]	O(n)
Trace back	O(n)

Plain recursion on the same recurrence can take exponential time, because OPT(j−1) and OPT(p(j)) share sub-calls; the table computes each value once. When all weights are equal the DP and earliest finish give the same count (Demo: all weights 1), which is why the unweighted problem needs no table.

See also: 0/1 Knapsack (skip or take, with a capacity instead of time overlaps), Longest Increasing Subsequence (another 1-D DP sped up by binary search) and Binary Search.

What the page leaves out

Memoized top-down recursion; jobs with equal finish times beyond a fixed tie order; several machines (interval partitioning, where a weighted version needs min-cost flow); jobs that may move within a window (scheduling with deadlines); the version where p(j) is computed by one merge-like sweep over jobs sorted by start time.

References

Interval scheduling (Wikipedia)

Kleinberg and Tardos, Dynamic Programming I: weighted interval scheduling (lecture slides)

Dynamic programming (Wikipedia)