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.

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.

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
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.
8. 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.