Interval Scheduling
GreedyEasyGreedily select maximum mutually compatible interval segments.
Alt+Shift+I
Configuration Panel
Maximum Compatible Scheduling (Track 0 selected, Track 1 overlapping)
Timeline is empty.
Time Complexity
O(N log N) sorting + O(N) sweep
Space Complexity
O(N) mapping intervals storage
Conceptual Overview
The Interval Scheduling problem finds the maximum number of mutually compatible intervals from a given set of intervals.
Greedy Choice Property
Sort intervals by end time ascending. Select the first interval, then select the next non-overlapping interval that finishes earliest.
Optimal Substructure
Selecting the earliest finishing interval leaves the maximum subset of remaining intervals available for subsequent scheduling.
Proof Idea / Correction
Proof by induction: selecting any other interval can only equal or reduce the set of compatible remaining intervals compared to selecting the earliest ending one.
Source: CP-Algorithms greedy reference