Weighted Interval Scheduling

Motivation

Take the interval scheduling problem and add a weight \(v_i\) to each interval — the value or revenue of accepting it. The goal becomes: pick a non-conflicting subset of intervals with maximum total weight, not maximum count.

The simple greedy that worked in the unweighted case (earliest finish time) fails here: a single high-value long interval can be worth more than two short low-value ones, but earliest-finish picks the short ones first. A natural reflex is to try a different greedy ordering, but no greedy works for this problem in the worst case.

The right tool is dynamic programming. The DP recurrence is short and elegant, the algorithm runs in \(\Theta(n \log n)\), and the problem is the standard introductory example of how DP succeeds where greedy fails (Kleinberg and Tardos 2005).

Problem

Given \(n\) intervals, the \(i\)-th with start time \(s_i\), finish time \(f_i\), and non-negative value \(v_i\). Two intervals conflict if their time ranges overlap. Find a subset \(S\) of pairwise non-conflicting intervals maximizing \(\sum_{i \in S} v_i\).

Key Ideas

Why greedy fails

Consider four intervals with finish times \(1, 2, 3, 4\) and values \(1, 1, 1, 100\). Greedy by earliest finish time picks intervals \(1, 2, 3\) (values summing to \(3\)). The optimum is just interval \(4\) alone (value \(100\)). No fixed greedy heuristic — earliest finish, smallest start, largest value, smallest length — can know in advance that the long, late interval is worth more than several short early ones. Greedy commits to a local rule, but the global optimum depends on a comparison that requires looking ahead.

A binary choice unlocks DP

For each interval \(i\), an optimal solution either uses \(i\) or it does not. Crucially, these two cases lead to disjoint subproblems:

  • If \(i\) is in the optimum, every other selected interval must end before \(s_i\) — and is therefore drawn from the strictly smaller subproblem of intervals that don’t conflict with \(i\).
  • If \(i\) is not in the optimum, the answer is the same as the best subset over the remaining intervals \(\{1, \ldots, i-1\}\).

This binary split is the source of the DP. Both branches reduce to a smaller version of the same problem, and the answer is the max of the two branches. Because each subproblem is defined by a single index \(i\), there are only \(n+1\) subproblems and the recurrence is computable in linear time.

The ordering by finish time matters: after sorting by \(f_i\), the subproblem “intervals compatible with \(i\)” is always a prefix \(\{1, \ldots, p(i)\}\), which collapses the indexing.

Deriving the Solution

Sort the intervals by finish time so \(f_1 \le f_2 \le \dots \le f_n\). Define \(p(i)\) = the largest index \(j < i\) such that interval \(j\) does not conflict with interval \(i\) (i.e., \(f_j \le s_i\)); \(p(i) = 0\) if no such \(j\) exists.

Let \(\text{OPT}(i)\) be the maximum total value attainable using only intervals \(\{1, 2, \dots, i\}\). The binary-choice argument from Key Ideas gives:

  • If \(i\) is included, the rest of the solution comes from intervals \(\{1, \dots, p(i)\}\): value \(v_i + \text{OPT}(p(i))\).
  • If \(i\) is excluded, the optimal uses only \(\{1, \dots, i-1\}\): value \(\text{OPT}(i-1)\).

So \[ \text{OPT}(i) = \max\left( v_i + \text{OPT}(p(i)), \; \text{OPT}(i-1) \right), \] with \(\text{OPT}(0) = 0\). The answer is \(\text{OPT}(n)\).

A naive top-down recursion on this recurrence is exponential — each call branches into two with no overlap-detection — but memoization or bottom-up iteration over a single array of length \(n+1\) collapses the work to linear after the sort.

Algorithm

sort intervals by finish time
compute p(i) for every i (binary search on finish times)
M[0] = 0
for i = 1 to n:
    M[i] = max(v_i + M[p(i)], M[i-1])
return M[n]

To recover the chosen intervals, walk back through the DP table: at each \(i\), check whether \(v_i + M[p(i)] > M[i-1]\); if so, include \(i\) and continue from \(p(i)\), otherwise continue from \(i-1\).

Walkthrough

Six intervals with predecessors

Six intervals sorted by finish time, with values \(v_i\) and predecessors \(p(i)\). The DP table \(M[i]\) is filled left to right; the optimal solution traces back through the chain \(6 \to p(6) = 4 \to \dots\) until reaching \(0\).

1 ✓ v=4, p=0 2 v=2, p=0 3 ✓ v=8, p=1 4 v=10, p=0 5 v=3, p=2 6 ✓ v=6, p=4 0 1 2 3 4 5 6 7 8 9 10 DP table i 1 2 3 4 5 6 p(i) 0 0 1 0 2 4 M[i] 4 4 12 12 12 18 accepted: {1, 3, 6} with values 4 + 8 + 6 = 18.

The high-value interval \(4\) (\(v = 10\)) covers the bulk of the timeline by itself, but accepting it forecloses both \(3\) (\(v = 8\)) and \(6\) (\(v = 6\)). The DP discovers that \(3 + 6 = 14\) paired with the early interval \(1\) (worth \(4\)) yields \(18\), beating \(4\)’s solo \(10\). Greedy by value (\(v\)) would have picked \(4\) first and lost \(8\) of value; only the systematic comparison \(\text{OPT}(i) = \max(v_i + \text{OPT}(p(i)), \text{OPT}(i - 1))\) catches the better trade.

Correctness

By induction on \(i\). The base case \(\text{OPT}(0) = 0\) is trivial — the empty subset has total value \(0\). Inductively, suppose \(M[j] = \text{OPT}(j)\) for all \(j < i\). Any optimal solution over \(\{1, \ldots, i\}\) either contains \(i\) or does not:

  • If it contains \(i\), its remaining intervals form an optimal solution over \(\{1, \ldots, p(i)\}\), which by the inductive hypothesis has value \(M[p(i)]\). Total: \(v_i + M[p(i)]\).
  • If it does not contain \(i\), it is an optimal solution over \(\{1, \ldots, i-1\}\), with value \(M[i-1]\).

The recurrence takes the max of these two cases, so \(M[i] = \text{OPT}(i)\).

Complexity and Tradeoffs

  • Sorting: \(O(n \log n)\).
  • Computing \(p(i)\): each requires a binary search on finish times, \(O(n \log n)\) total.
  • Filling the DP table: \(O(n)\).
  • Total: \(\Theta(n \log n)\).

Space is \(O(n)\) for the DP table; the optimal subset can be reconstructed in an additional \(O(n)\) pass.

Memoization vs. iteration. The same recurrence can be implemented top-down with memoization. Both strategies have the same asymptotic complexity; the bottom-up table fill is more cache-friendly and produces a single contiguous array of values useful for reconstructing the solution.

When to Use It

Situation Approach
Intervals all weighted equally Use unweighted interval scheduling — earliest-finish greedy, \(O(n \log n)\) with simpler code.
Weighted intervals on a line (this problem) Weighted interval scheduling DP, \(\Theta(n \log n)\).
Weighted intervals on multiple machines Reduce to a flow or LP — DP doesn’t capture the assignment cleanly.
Online arrivals (decide on the fly) Use a competitive algorithm; the offline DP needs the full input upfront.
Costs in addition to values Generalize the DP with both quantities; the same recurrence structure works.

References

Kleinberg, Jon, and Éva Tardos. 2005. Algorithm Design. Pearson/Addison-Wesley. https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259.