Medium Problemsoptimizationlinear

Weighted Job Schedulling

Given n jobs, each with a start time, an end time, and a profit, choose a subset of non-overlapping jobs that maximizes the total profit collected.

Do this lesson first: house robber

Example input

6 jobs sorted by end time, as [start, end, profit] triples

Expected output

170

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = max(dp[i - 1], profit[i] + dp[p(i)])

Ask what happened to the last job in the sorted prefix. Either you did not take it, in which case the best is whatever the previous prefix already achieved, or you did, in which case you collect its profit and add the best schedule that finishes before it starts. Those two cases cover every possibility with no overlap, so a max over them is the answer. The second case is the interesting one: p(i) is the latest job whose end time is at or before job i's start, which is almost never i - 2 and sometimes does not exist at all.

The jobs must be sorted by END time before anything else happens, and that sort is what makes the recurrence valid: it guarantees every job compatible with job i sits somewhere to its left, so p(i) is always an index already filled. dp[0] is the first job's profit, since with one job the only choice is to take it. Filling left to right then works because both dp[i - 1] and dp[p(i)] are smaller indices.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

The jobs must be sorted by END time before anything else happens, and that sort is what makes the recurrence valid: it guarantees every job compatible with job i sits somewhere to its left, so p(i) is always an index already filled. dp[0] is the first job's profit, since with one job the only choice is to take it. Filling left to right then works because both dp[i - 1] and dp[p(i)] are smaller indices.

i=0

i=1

i=2

i=3

i=4

i=5

50

110

140

170

weighted-job-scheduling.ts

1function schedule(jobs) {
2 jobs.sort((a, b) => a.end - b.end);
3 const dp = [jobs[0].profit];
4 for (let i = 1; i < jobs.length; i++) {
5 const p = latestBefore(jobs, i);
6 const take = jobs[i].profit + (p >= 0 ? dp[p] : 0);
7 dp[i] = Math.max(dp[i - 1], take);
8 }
9 return dp[jobs.length - 1];
10}

Base caseComputedBeing readAnswer

The code, the trap, the variations

weighted-job-scheduling.ts

1function schedule(jobs) {
2 jobs.sort((a, b) => a.end - b.end);
3 const dp = [jobs[0].profit];
4 for (let i = 1; i < jobs.length; i++) {
5 const p = latestBefore(jobs, i);
6 const take = jobs[i].profit + (p >= 0 ? dp[p] : 0);
7 dp[i] = Math.max(dp[i - 1], take);
8 }
9 return dp[jobs.length - 1];
10}

Where people go wrong

Sorting by start time, or by profit, instead of by end time. Sorting by profit is the greedy instinct and it fails immediately: one fat job spanning the whole day beats nothing else, but two thinner jobs beside each other often beat it. Sorting by start time is subtler and looks fine until you notice it gives no guarantee that a compatible predecessor sits to the left, which is the single property the whole recurrence rests on.

Every job has the same profit, so you just want as many jobs as possible.
The recurrence is unchanged in shape; profit[i] becomes 1. That is the classic activity-selection problem, and it is the one case where a greedy rule (always take the next job that ends earliest) happens to be optimal, which is worth knowing precisely because the weighted version defeats it.
You may run two jobs at once, on two machines.
One number no longer names the state. You need the finishing times of both machines, so the table gains a dimension. The last-decision split survives untouched; only what it takes to describe a state grows.

Largest Divisible Subset 0-1 Knapsack Problem