Interval Scheduling

Interval scheduling is a greedy algorithm for choosing the largest possible set of non-overlapping intervals on one resource. Sort the intervals by finish time, accept the first compatible one, and repeat. The result is optimal for the unweighted problem, with O(n log n) time complexity from the sort.

Picture one meeting room and a pile of requests. The meeting that starts earliest is not necessarily helpful; it may occupy the room all day. The meeting that finishes earliest hands the room back soonest. Starting early sounds virtuous. Calendars do not award virtue.

How interval scheduling works

Write each request as a half-open interval [start, end). Half-open means a meeting ending at time 5 and another starting at time 5 are compatible. They touch, but they do not overlap.

The algorithm keeps one scalar, last_end, which is the finish time of the most recently accepted interval. After sorting by end, scan from left to right:

1. If start >= last_end, accept the interval and set last_end = end.
2. If start < last_end, reject it and leave last_end alone.

That second line matters. A rejected interval never changes the schedule, so it cannot move the compatibility fence.

Why does earliest finish give an optimal answer? Take any optimal schedule and compare its next interval with the greedy choice. The greedy interval finishes no later, because it was first in finish-time order. Replace the optimal schedule's interval with the greedy one. Every later interval that fit before still fits now, and the number of selected intervals has not changed. Repeat the exchange on the remaining suffix. Eventually the optimal witness has become the greedy schedule without losing a single interval.

The witness on the proof rail is one concrete stand-in for an arbitrary optimal schedule O, not the only schedule covered by the argument. The same exchange works at each position of any O. Count never changes, so after O has become the greedy schedule, the two schedules have the same size. Since O was optimal, no schedule can contain more than greedy. That closes the upper bound: four is not merely a count we found; no schedule can contain five.

This is the greedy method at its cleanest: the code makes a local choice, while the exchange argument proves that the local choice cannot damage the global optimum.

Interval scheduling step by step

The default input arrives in this order:

A=[0,3), B=[5,7), C=[1,2), D=[6,9), E=[3,5), F=[4,6), G=[7,9), H=[2,5).

Sorting by finish time, then by start time for deterministic ties, produces:

C, A, H, E, F, B, D, G.

Now scan that order.

1. C=[1,2) is first. Accept it and set last_end = 2.
2. A=[0,3) starts at 0, which is before 2. Reject it; last_end stays 2.
3. H=[2,5) starts exactly at 2. Because the intervals are half-open and the guard is >=, accept it and set last_end = 5.
4. E=[3,5) starts before 5. Reject it.
5. F=[4,6) also starts before 5. Reject it.
6. B=[5,7) touches the current fence at 5. Accept it and set last_end = 7.
7. D=[6,9) starts before 7. Reject it.
8. G=[7,9) touches the fence at 7. Accept it and set last_end = 9.

The greedy schedule is C, H, B, G, so it keeps four intervals and removes four.

The proof rail begins with a different optimal schedule: A, E, B, G. Replace A with C. Since C ends at 2 and A ends at 3, the suffix still fits. Next, replace E with H; both end at 5, so again nothing later is lost. The two remaining choices already agree. The witness has turned into C, H, B, G and still contains four intervals, which proves the greedy result is optimal.

On this particular input, A, E, B, G is also the schedule produced by sorting by earliest start. It ties the correct rule here, but that coincidence is not a proof. Open the Long blocker scenario to see earliest-start keep one interval while earliest-finish keeps seven.

The removal version is the same objective viewed from the other side: minimum removals = n - maximum compatible count. This is the form used by LeetCode 435, Non-overlapping Intervals.

On the canvas, the vertical last_end fence is the invariant. Accepted intervals move into the chosen rail and advance the fence. Rejected intervals expose their overlap and leave the fence motionless.

Time and space complexity

If the intervals are already sorted by finish time, the scan alone is O(n). The displayed implementation copies the input into ordered and stores the selected schedule in chosen, so it uses O(n) space. The running greedy state beyond those arrays is just last_end, or O(1).

Edge cases

• Empty input. The algorithm returns an empty schedule. The editor requires at least one interval, but the step generator still handles this boundary.
• One interval. It is accepted immediately.
• Every interval overlaps. Exactly one interval is selected: the one with the earliest finish.
• Touching endpoints. [0,2) and [2,4) are compatible. This is why the guard uses >=, not >.
• Equal finish times. Either tied interval is safe for cardinality. The lesson breaks ties by start time and then stable input order so the trace is deterministic.
• Weighted intervals. If intervals have unequal values and the goal is maximum total value, this greedy rule solves the wrong problem. Weighted interval scheduling uses dynamic programming.

Common mistakes

• Sorting by earliest start. A request can start first and occupy the resource for the entire day. The Long blocker scenario keeps one interval under earliest-start but seven under earliest-finish.
• Sorting by shortest duration. A short interval can sit in the middle of the timeline and block useful choices on both sides. Duration is not the exchange-safe key.
• Using start > last_end. That rejects legal back-to-back intervals.
• Updating last_end after a rejection. The fence belongs to the last accepted interval. Moving it for a rejected request corrupts every later decision.
• Mixing closed and half-open intervals. If your domain treats both endpoints as occupied, equality may mean conflict. Pick one interval convention and make the comparison match it.
• Claiming the proof covers weights. The exchange argument preserves the number of intervals, not an arbitrary sum of interval values.