Weighted Interval Scheduling

A single room or machine can run only one job at a time. When every accepted job is worth the same amount, an earliest-finish greedy scan maximizes the number of jobs. Different values change the question: a single valuable job can be better than several short ones. Weighted interval scheduling finds a compatible subset with the greatest total value.

Represent a job by [start, finish) and its value. The finish is excluded, so one job may start exactly when another finishes. This explorer uses positive durations, integer times from 0 to 20 and nonnegative integer values from 0 to 99. Its fixed time axis shows duration; the numerical value appears in each row.

A choice with a compatible prefix

Sort jobs by increasing finish, breaking equal finishes by their original input ID. Let p(j) be the largest earlier sorted index whose finish is at most the start of job j; use 0 if none exists. Let M(j) be the best value among the first j sorted jobs, with M(0) = 0.

M(j) = max(M(j − 1), value(j) + M(p(j)))

Every optimal schedule either excludes j, leaving the first j − 1 jobs, or includes j. In the latter case all its other jobs lie in the compatible prefix ending at p(j). Conversely, either branch constructs a feasible schedule. Taking the larger value therefore gives an optimum by induction. Sorting makes each referenced prefix earlier than the current decision.

Worked example: four jobs, two different objectives

The original Greedy trap has J1 = [0, 3), value 4; J2 = [3, 5), value 4; J3 = [0, 5), value 11; and J4 = [5, 7), value 3. Equal finishes put J2 before J3 because its original ID is smaller. Calculate both branches before moving the controls:

j / job	p(j)	Include	Exclude	M(j)	Chosen prefix
0 / none	—	—	—	0	None
1 / J1	0	4 + 0 = 4	0	4	J1
2 / J2	1	4 + 4 = 8	4	8	J1, J2
3 / J3	0	11 + 0 = 11	8	11	J3
4 / J4	3	3 + 11 = 14	11	14	J3, J4

Earliest-finish greedy selects J1, J2 and J4: three jobs worth 4 + 4 + 3 = 11. The value optimum selects J3 and J4: two jobs worth 11 + 3 = 14. Independently, a schedule containing J3 cannot contain J1 or J2 and can add only J4, reaching 14. Without J3, all remaining jobs fit and total only 11. These two exhaustive cases prove 14 is optimal without relying on the displayed DP output.

The prefix selection can change: evaluating J3 replaces J1 and J2. Green does not mean an irrevocable greedy acceptance. The implementation includes a job only when its include branch is strictly larger. On equality it excludes that job, selecting one reproducible optimum rather than claiming uniqueness.

Experiment: predict, replace, rewind

Open the Weighted Interval Scheduling explorer. Use the visible numerical cards together with the timeline and the horizontally scrollable decision table.

Press Reset experiment. Job example is Greedy trap and Jobs contains the four rows above. Evaluated jobs is 0, status Ready, both prefix values are 0, and Total optimum is Pending. Future M cells say Pending.
Set Evaluated jobs to 2. Read best prefix 8, selected J1, J2 and greedy 8. Current J2 has predecessor index 1, include 8 and exclude 4. This is an optimum for two evaluated jobs, not yet a certificate for the whole input.
Press Next decision. J3 compares include 11 with exclude 8; the chosen prefix becomes J3 and greedy stays at 8. Press Finish decisions: read total optimum 14, chosen J3, J4 and greedy 11.
Press Previous decision to recover the prefix at 3, with best 11 and Total optimum Pending. Press Rewind decisions to return to Ready. The Jobs text stays unchanged.
Choose Equal profit in Job example, then finish. Include 8 equals exclude 8 at J3; Exclude (tie) keeps J1, J2. J3 alone has the same value, so the chosen subset is not unique. Try Touching endpoints and finish: all three jobs fit, total 9.
Choose Mixed input order and finish. The sorted original IDs are J3, J4, J1, J2, and the optimum is 9 with J3, J4, J2. The last predecessor index 2 refers to original J4, not J2. Choose All overlap and finish: J2 alone is worth 7.
Replace Jobs with two lines, 0 1 0 and 1 2 0. Editing immediately resets the prefix to 0. Finish: best value 0 and chosen None; greedy still takes J1, J2, also worth 0. Choose Empty jobs: the empty input is already Complete with total 0 and disabled navigation.
Enter 2 2 5 in Jobs. Zero duration is invalid, the text remains visible, stale results disappear and navigation is disabled. Press Reset experiment to recover the four original jobs. Resize the window: IDs, values and evaluated prefix stay the same.

What the certificate covers

The model assumes one resource, fixed positive-duration jobs, no setup or travel time, no preemption and additive nonnegative values. It optimizes total value, not the number or total duration of jobs. The earliest-finish comparator is useful for demonstrating the difference; it is not a value-optimal algorithm. Multiple resources and online arrivals need other models.

The editor accepts at most eight nonblank rows and 512 characters. Each row needs exactly three unsigned ASCII integers, separated by spaces or tabs. Leading zeros, padding and blank lines are accepted; negative signs, decimal or exponent notation, extra fields and values outside the stated bounds are rejected. A bad row invalidates the entire input. Native textarea line endings are normalized. There is no clipping or clamping of numeric results: eight compatible jobs worth 99 each total exactly 792.

The empty schedule is allowed. Zero-valued jobs may be omitted even when compatible; duplicate rows remain distinct jobs that conflict when their intervals overlap. At an include/exclude tie this explorer keeps exclude. A future DP cell is Pending, and Total optimum is withheld until every job has been evaluated. p(j), however, depends only on the input and may be read before replaying a decision.

Sorting and binary-search predecessor computation take O(n log n), the scalar recurrence takes O(n) time and storage, and reconstructing the currently displayed subset takes O(n). The greedy prefix comparator also scans at most n jobs. The small bound keeps every exact integer calculation inspectable. Native vertical scrolling reaches all panels, and horizontal table scrolling preserves full-size numerical columns on narrow screens.

References and independently checked examples

The course notes support the problem, compatible-predecessor definition and recurrence. The four-job counterexample, tie policy and editor limits are original teaching choices here; the references do not contain or endorse these exact presets.

Cornell CS482: Dynamic Programming, page 2, derives weighted interval scheduling from the include/exclude split and M(0) = 0.
Cornell CS4820: Computing p(j) defines half-open jobs and the largest earlier compatible finish index. Its two-pointer algorithm is a different way to compute predecessors; this explorer uses binary search.

Compare the related maximum-count Interval Scheduling and Knapsack Problem explorers: count, compatible time and capacity are different constraints and objectives.

Weighted Interval Scheduling