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.

The greedy rule and its endpoint convention

Write a job as a half-open interval [s, f), with s < f. It occupies its start but excludes its finish, so [1, 2) and [2, 3) are compatible. Sort jobs by increasing finish time, breaking exact ties by their original ID. Accept the first job, then accept each later job whose start is at least the finish of the most recently selected job. A rejected job does not change that finish.

The complete scan gives a maximum-cardinality compatible subset. A partial scan shows only selected-so-far jobs: stopping early does not establish the final answer. Equal finish times can permit different optimal subsets; the deterministic ID tie-break makes this explorer reproducible, rather than claiming a unique optimum.

Worked example: touching jobs beat one long job

The Touching endpoints preset contains ID 0: [0, 6), ID 1: [1, 2), ID 2: [2, 3), ID 3: [3, 4) and ID 4: [4, 5). Compute the finish order before running the explorer: 1, 2, 3, 4, 0.

Considered	ID	Interval	Decision	Last finish
1	1	[1, 2)	Accept first	2
2	2	[2, 3)	Accept: 2 ≥ 2	3
3	3	[3, 4)	Accept: 3 ≥ 3	4
4	4	[4, 5)	Accept: 4 ≥ 4	5
5	0	[0, 6)	Reject: 0 < 5	5

After two decisions the selection is only IDs 1 and 2, with last finish 3. After all five decisions the result is IDs 1, 2, 3 and 4: four jobs. The long job overlaps every short job, so any schedule containing it has only one job. The four short jobs fit together, and there are only four of them. These observations independently establish that four is optimal. Choosing the earliest start would have selected the long job and missed this optimum.

Why earliest finish is safe

Let g be an earliest finishing job, and take an optimal nonempty schedule whose first job is o. Replacing o with g preserves the number of jobs: g finishes no later than o, so every later job in that schedule still starts after g has finished. Thus some optimum starts with g. Apply the same exchange argument to the jobs compatible with g, and repeat. The argument depends on maximizing the number of jobs, not their values or total duration.

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.

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.
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.
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.
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.
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.
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.
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.
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.

What this result assumes

The model has one resource, positive-length jobs with fixed endpoints, and equal value for every accepted job. Time is in arbitrary units. Touching endpoints are allowed by the half-open convention. Real setup times, travel, multiple resources and job priorities require different models.

Weighted interval scheduling maximizes total value and needs a different algorithm. Interval partitioning asks how many resources are required to accommodate all jobs. Neither is the maximum-count subset problem shown here.
The seeded generator uses two successive mulberry32 draws per original ID: start is 80 times the first draw, length is 5 plus 15 times the second, and finish is start plus length. Count is bounded from 5 to 30 and seed from 1 to 100. The explorer does not accept arbitrary typed intervals.
Sorting and compatibility use full floating-point values; three-decimal labels are rounded for reading. Do not infer an exact tie from rounded labels. The small touching and equal-finish presets use exact integer endpoints.
The core method sorts in O(n log n) time and then scans in O(n). This teaching implementation also retains all prefix selections for reversible replay, requiring additional bounded snapshot storage. Animation speed changes wall-clock cadence only.
Thirty rows remain at a readable CSS font size and are reached by native scrolling. They are not squeezed into one screen. Green means accepted, rose means rejected, gray means pending, and an amber outline marks the current row. The selected-so-far count is a completed optimum only when the phase says Finished.

Course references and the original examples

The references support the greedy rule, its exchange argument and the problem conventions. The five-job worked preset and seeded numeric results above are independently checked Riano examples.

Charles Cusack, Hope College: Interval Scheduling explains earliest-finish selection and the exchange argument, including equal finishes and distinctions from weighted and multiple-resource variants.
University at Buffalo CSE331: Notation for Scheduling Problems specifies half-open endpoints and separates the weighted scheduling objective from the unweighted compatible subset.

Interval Scheduling