218. Maximum Number of Non-overlapping Intervals

Why this mechanism works

The interval finishing earliest leaves at least as much room for future intervals as any alternative first choice. After selecting it, solve the same problem among intervals starting at or after its end. Sorting once allows this repeated exchange argument to become one scan.

State and boundaries

selected is a compatible sequence. last_end is its final endpoint; an interval is available exactly when start>=last_end.

Protocol

1. Sort indexed intervals by finishing time and tie keys.
2. Begin with no chosen endpoint.
3. Accept each interval whose start is compatible.
4. Update last_end only on acceptance.
5. Return the selected sequence.

Visualization

[1,4), [2,3), [3,5), [5,6)
choose [2,3), then [3,5), then [5,6)
earliest start [1,4) would block the first two

Python implementation

def select_intervals(intervals):
    ordered = sorted(enumerate(intervals), key=lambda item:
                     (item[1][1], item[1][0], item[0]))
    selected, last_end = [], None
    for _, (start, end) in ordered:
        if last_end is None or start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L3 <lambda>: (item[1][1], item[1][0], item[0]))
item=(0, (1, 4))

L3 <lambda>: (item[1][1], item[1][0], item[0]))
item=(1, (2, 3))

L3 <lambda>: (item[1][1], item[1][0], item[0]))
item=(2, (3, 5))

L3 <lambda>: (item[1][1], item[1][0], item[0]))
item=(3, (5, 6))

L2 select_intervals: ordered = sorted(enumerate(intervals), key=lambda item:
intervals=[(1, 4), (2, 3), (3, 5), (5, 6)]; ordered=[(1, (..., ...)), (0, (..., ...)), (2, (..., ...)), (3, (..., ...))]

L4 select_intervals: selected, last_end = [], None
intervals=[(1, 4), (2, 3), (3, 5), (5, 6)]; ordered=[(1, (..., ...)), (0, (..., ...)), (2, (..., ...)), (3, (..., ...))]; selected=[]; last_end=None

L5 select_intervals: for _, (start, end) in ordered:
intervals=[(1, 4), (2, 3), (3, 5), (5, 6)]; ordered=[(1, (..., ...)), (0, (..., ...)), (2, (..., ...)), (3, (..., ...))]; selected=[]; last_end=None; _=1; start=2; end=3

L7 select_intervals: selected.append((start, end))
intervals=[(1, 4), (2, 3), (3, 5), (5, 6)]; ordered=[(1, (..., ...)), (0, (..., ...)), (2, (..., ...)), (3, (..., ...))]; selected=[(2, 3)]; last_end=None; _=1; start=2; end=3

... 4 intermediate state changes omitted ...

L8 select_intervals: last_end = end
intervals=[(1, 4), (2, 3), (3, 5), (5, 6)]; ordered=[(1, (..., ...)), (0, (..., ...)), (2, (..., ...)), (3, (..., ...))]; selected=[(2, 3), (3, 5)]; last_end=5; _=2; start=3; end=5

L5 select_intervals: for _, (start, end) in ordered:
intervals=[(1, 4), (2, 3), (3, 5), (5, 6)]; ordered=[(1, (..., ...)), (0, (..., ...)), (2, (..., ...)), (3, (..., ...))]; selected=[(2, 3), (3, 5)]; last_end=5; _=3; start=5; end=6

L7 select_intervals: selected.append((start, end))
intervals=[(1, 4), (2, 3), (3, 5), (5, 6)]; ordered=[(1, (..., ...)), (0, (..., ...)), (2, (..., ...)), (3, (..., ...))]; selected=[(2, 3), (3, 5), (5, 6)]; last_end=5; _=3; start=5; end=6

L8 select_intervals: last_end = end
intervals=[(1, 4), (2, 3), (3, 5), (5, 6)]; ordered=[(1, (..., ...)), (0, (..., ...)), (2, (..., ...)), (3, (..., ...))]; selected=[(2, 3), (3, 5), (5, 6)]; last_end=6; _=3; start=5; end=6

L2 select_intervals: ordered = sorted(enumerate(intervals), key=lambda item:
intervals=[]; ordered=[]

L4 select_intervals: selected, last_end = [], None
intervals=[]; ordered=[]; selected=[]; last_end=None

Why the solution is correct

Take an optimum solution's first interval. Replacing it with the earliest-finishing available interval cannot overlap any later selected interval, because its end is no later. Thus an optimum exists containing the greedy choice. Applying the same exchange to the remaining suffix proves maximum cardinality.

Time and space

O(n log n) time and O(n) sorting/output storage.

Common mistakes

Choosing earliest start can select a long interval that blocks many short ones. Using start>last_end incorrectly rejects touching half-open intervals.

Reasoning card

Transfer exercise

Assign each interval a value and maximize total value. Explain why earliest finish alone no longer proves optimality.