Interval Scheduling

A room, machine or other single resource can handle only one job at a time. Each job has a fixed start and finish. Which compatible subset contains the most jobs? For this unweighted problem, choosing the earliest finishing available job leaves the most room for later choices.

Experiment: predict, scan and reverse a decision

Open the Interval Scheduling explorer. The timeline lists original IDs in finish order; its bars and numerical decision table describe the same data. Pending rows have not yet been considered.

1. Set Interval example to Touching endpoints. Read five intervals, considered zero, no current ID, no selected IDs and no last finish. Count and seed are disabled because this preset is fixed.
2. Press Next interval twice. Read considered 2, current ID 2, selected IDs 1, 2 and last finish 3. The second interval is accepted even though its start equals the previous finish.
3. Press Previous interval: only ID 1 remains and the last finish returns to 2. Next interval restores the second decision. Finish scan gives four jobs; Rewind scan clears the prefix. You can also seek directly with Considered intervals.
4. Choose Equal finishes, then Finish scan. The order is 0, 1, 3, 2, 4 and selected IDs are 0, 3, 4. At considered 2, ID 1 is rejected because its start 1 is below the selected finish 2. Choose All overlap and finish: only ID 0 is selected.
5. Choose Seeded intervals, set Intervals to 15 and Random seed to 42, then finish. The selected IDs are 9, 2, 14, 0, 10, count 5, with last finish displayed as 72.755. Repeating these settings reproduces every interval.
6. Try count 5 and seed 1: finish with IDs 4, 2 and count 2. Try count 30 and seed 100: finish with IDs 3, 0, 29, 5, 28, 14, 26 and count 7. Scroll the timeline vertically to reach every row; the decision table scrolls horizontally on a narrow screen.
7. Use Rewind scan, then Play scan and Pause scan. Change Animation speed between 1 and 100 to change the delay between decisions, not the answer. Playing from a finished scan starts over. Manual navigation and changes to the example, count or seed cancel playback and rewind when data changes.
8. Press Reset experiment. It restores Seeded intervals, count 15, seed 42, speed 50 and the empty Ready prefix. Resizing the window changes the chart layout without changing its data or selected prefix.