The site's fifth dynamic programming entry, and the answer to a question Activity Selection's own Pitfalls section left open: what happens once activities stop being interchangeable? Give every activity a weight — a room booking's revenue, a job's payoff, whatever makes one activity worth more than another — and change the goal from "accept as many activities as possible" to "accept the subset with the highest total weight." Activity Selection's finish-time greedy rule, provably optimal for maximizing count, stops being correct the moment weights differ: a single high-value activity can be worth skipping several lower-value ones for, and finish time alone can't see that. This page closes that forward reference with a dynamic-programming recurrence instead — over the same finish-time-sorted order, but with a real either/or decision per activity in place of a one-pass greedy walk.
Activity Selection's own eleven-activity default
dataset, unchanged, with one weight added: activity 10 [2,14] is worth 20, and
every other activity stays at the default weight of 1. Press Step or
Run to watch dp[i] fill in left to right: each cell holds the best total weight
achievable using only the first i activities (in finish-time order). For each activity the demo
also finds its predecessor — the latest earlier activity that doesn't overlap it — by binary
search over the already-sorted finish times, the same narrowing
Binary Search itself uses, just searching for a boundary instead
of an exact value. Once the array is full, the demo backtracks from dp[11] to recover which
activities are actually in the optimal set — watch the timeline bars light up green (taken) or fade
(skipped). A comparison line underneath, filled in once the run is done, shows what Activity Selection's own
earliest-finish-time greedy would have picked on this exact same weighted data, and how much total weight it
leaves on the table.
timeline (sorted by finish time)
Sort every activity by finish time first, same as Activity Selection — call the sorted order
1..n. The base case is trivial: with zero activities available, dp[0] = 0, nothing
to choose from yet. From there, every activity i faces exactly one yes-or-no question, the same
shape 0/1 Knapsack's own recurrence asks of every item: is activity
i in the optimal set or not? Skip it, and the best achievable is whatever it was
without it, dp[i-1]. Take it, and the best achievable is its own weight plus the
best achievable among activities that don't conflict with it — every activity that finishes at or before
i starts. That compatible set is always a prefix of the sorted order (finishing earlier keeps an
activity eligible), so it has a well-defined latest member: call it p(i), found by binary search
since the finish times are already sorted. Taking activity i is worth
weighti + dp[p(i)]. The recurrence keeps whichever option is better:
dp[i] = max(dp[i-1], weighti + dp[p(i)]). Both branches only ever depend on strictly
smaller subproblems already solved, the same optimal-substructure argument every dynamic-programming page on
this site makes — here with a binary search standing in for the array-index arithmetic
0/1 Knapsack uses to find its own "one item back" cell.
On this page's own dataset, activity 10 [2,14] (weight 20) overlaps every other
activity except activity 11 [12,16], which starts before it finishes anyway (12 <
14) and so is never actually compatible either — activity 10 is compatible with nothing at all in this
particular set. The DP correctly finds that taking activity 10 alone (20) beats every combination
that leaves it out, including the four-activity set {1, 4, 8, 11} that maximizes count — the exact set
Activity Selection's own greedy proof shows is optimal
when every weight is equal — confirmed against an independent brute-force search over all 2¹¹
subsets, not just asserted.
Builds the array left to right, finding each activity's predecessor by binary search, then walks it backward from the last cell to recover which activities were actually chosen:
function weightedIntervalScheduling(activities) {
const sorted = [...activities].sort((a, b) => a.end - b.end);
const n = sorted.length;
// binary search for the latest earlier activity that finishes at or before sorted[i-1].start
function predecessor(i) {
const target = sorted[i - 1].start;
let lo = 0, hi = i - 2, result = 0;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (sorted[mid].end <= target) { result = mid + 1; lo = mid + 1; }
else hi = mid - 1;
}
return result; // 1-indexed; 0 means "no compatible activity before this one"
}
const p = new Array(n + 1).fill(0);
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
p[i] = predecessor(i);
dp[i] = Math.max(dp[i - 1], sorted[i - 1].weight + dp[p[i]]);
}
// backtrack from the last cell to recover which activities were taken
let i = n;
const chosen = [];
while (i > 0) {
if (dp[i] === dp[i - 1]) {
i--; // value didn't change by considering activity i — it wasn't used
} else {
chosen.push(sorted[i - 1]);
i = p[i];
}
}
chosen.reverse();
return { maxWeight: dp[n], chosen };
}Finish-time greedy still runs without complaint on weighted data — it just quietly stops being
optimal. Nothing about Activity Selection's
one-pass rule checks weight at all, so it happily returns an answer on this page's own dataset: activities 1,
4, 8, and 11, total weight 4 — the same count-maximizing set that page's own exchange-argument
proof guarantees is optimal, which is exactly the problem, since count is no longer the goal. The DP above
finds 20 — activity 10 alone — a 5× difference from skipping four activities
entirely to make room for the one expensive one greedy never reconsiders. Both numbers come from running the
exact code on this page, not a hand-picked illustration: press Run above and the comparison line reports both
live. As a sanity check in the other direction — not shown in the demo, checked separately — setting activity
10's weight back down to 1, matching everyone else, and rerunning this page's own DP on the
result recovers that identical {1, 4, 8, 11} set, confirming this recurrence genuinely generalizes activity
selection rather than just resembling it.
The predecessor binary search only works because the array is already sorted by finish
time. predecessor(i) assumes sorted[0..i-2]'s finish times are
non-decreasing and narrows a search range on that assumption alone — the same precondition
Binary Search's own Pitfalls section already flags for
its classic form. Skip the initial sort, or sort by anything other than finish time, and the binary search
still returns an index without erroring — just not necessarily the correct predecessor, silently
corrupting every dp[i] downstream of the first bad lookup.
A tie between skipping and taking is resolved by an arbitrary rule, not a fact the problem
forces — the same caveat 0/1 Knapsack's own Pitfalls
section raises about its backtracking. This page's backtrack checks dp[i] === dp[i-1] first,
so any exact tie is reported as "skipped." Checked directly, not just asserted: three activities
A[0,2] weight 5, B[3,5] weight 5, and C[0,6]
weight 10 (spanning both) all tie at total weight 10 two different ways —
{A, B} or {C} alone. This page's code always recovers {A, B}, since
dp[3] = dp[2] exactly and the skip branch is checked first; a version that checked "take" first
would recover {C} instead, an equally valid but different optimal set. The weight is
never ambiguous — the specific set the code reports can be.
Time: O(n log n) — sorting costs O(n log n), and each of the
n predecessor lookups costs O(log n) by binary search (a naive linear scan for each
predecessor would cost O(n) per lookup, O(n²) overall — the same
"binary search turns a linear scan into a logarithmic one" trade
Longest Increasing Subsequence makes
for its own predecessor search). Unlike 0/1 Knapsack's
O(n · capacity), this bound depends only on the number of activities, never on the numeric
magnitude of any start or end time — genuinely polynomial, not pseudo-polynomial. Space:
O(n) for the sorted copy, the predecessor array, and the DP array.
Weighted interval scheduling shows up anywhere Activity Selection's plain count-maximizing version is too blunt an objective: booking a single resource (a conference room, a machine, an ad slot) where different bookings pay different amounts, or choosing which non-overlapping jobs to run in a fixed maintenance window when each job has its own payoff. The recurrence itself — sort, then choose skip-or-take against a binary-searched predecessor — also generalizes past a single resource: job scheduling to minimize weighted lateness and other single-machine scheduling variants build on the same finish-time-ordered skip/take shape, though with a different per-job cost function than this page's fixed weight.
This site's guide, Choosing a Dynamic Programming Approach, compares this entry against the other ten Dynamic Programming entries side by side.