Weighted Interval Scheduling

Each interval has a value; select non-overlapping intervals maximising the total. Greedy fails here — this is a DP.

The algorithm — $O(n\log n)$

Sort by finish time. For each interval $i$, let $p(i)$ be the last interval that finishes at or before $i$ starts (found by binary search).

$dp[i]=\max (dp[i-1],v_i+dp[p(i)])$

— skip interval $i$, or take it and jump back to $p(i)$.

long long weightedIntervalScheduling(vector<array<long long,3>> iv) {   // {start, end, value}
    int n = iv.size();
    sort(iv.begin(), iv.end(), [](auto& a, auto& b){ return a[1] < b[1]; });
 
    vector<long long> ends(n);
    for (int i = 0; i < n; i++) ends[i] = iv[i][1];
 
    vector<long long> dp(n + 1, 0);
    for (int i = 0; i < n; i++) {
        int p = upper_bound(ends.begin(), ends.begin() + i, iv[i][0]) - ends.begin();
        dp[i + 1] = max(dp[i], iv[i][2] + dp[p]);
    }
    return dp[n];
}

Use upper_bound for half-open intervals (touching is allowed) and lower_bound when touching conflicts — the same convention question as in interval scheduling.

Why greedy fails

By value: one huge interval may block several that together are worth more. By value density: same problem. By finish time: ignores the values entirely.

The DP is necessary because the choice at each interval depends on the best achievable before it, which greedy cannot know.

Reconstruction

vector<int> chosen;
int i = n;
while (i > 0) {
    int j = i - 1;
    if (dp[i] == dp[i-1]) i--;                             // interval j was skipped
    else { chosen.push_back(j); i = p[j]; }                // taken
}
reverse(chosen.begin(), chosen.end());

Store the $p(i)$ values during the forward pass to avoid recomputing them.

Variants

Variant	Method	Cost
Unweighted (max count)	greedy by finish time	$O(n\log n)$
Weighted	this DP	$O(n\log n)$
At most $k$ intervals	dp[i][k]	$O(nk\log n)$
$k$ machines (parallel)	min-cost flow	$O(n^2\log n)$
Intervals on a circle	fix one interval as included/excluded; $O(n^2\log n)$
With setup times between intervals	adjust $p(i)$	$O(n\log n)$
Maximise the count, tie-break by weight	DP on a pair	$O(n\log n)$
Value depends on when it is scheduled	more general DP

$k$ machines

With $k$ parallel machines, greedy and the simple DP both break. Model as min-cost flow: a path along the time axis with capacity $k$, plus an arc for each interval from its start time to its end time with capacity 1 and cost $-v_i$. A min-cost flow of value $k$ selects the optimal set.

This “intervals as arcs over a time line with capacity $k$” construction is a genuinely reusable modelling pattern.

Generalisation: DP over a sorted axis

The structure — sort by one coordinate, binary search the last compatible predecessor, take the max — appears throughout:

Problem	The “predecessor”
Weighted interval scheduling	last interval finishing before this starts
LIS with weights	last smaller element
Longest chain of pairs	last compatible pair
Box stacking / Russian dolls	last fitting box
Job sequencing with deadlines	see that page
Maximum sum of non-adjacent elements	index $i-2$

When the predecessor is monotone, the binary search can be replaced by a two-pointer, giving $O(n)$ after the sort.

See also: Interval Scheduling · Introduction to DP · Min-Cost Flow