Interval Scheduling

Selects the maximum number of non-overlapping intervals from a set. Sorting by finish time (not start time) and greedily taking any interval compatible with the last accepted one is provably optimal — the classic exchange-argument proof.

Category: Greedy
Time complexity: O(n log n)
Space complexity: O(n)

Pseudocode

sort intervals by end time
lastEnd ← -∞
for each interval: if start ≥ lastEnd, accept it, lastEnd ← its end

Reference implementation

intervals.sort(key=lambda iv: iv.end)
last_end = float('-inf')
chosen = []
for s, e in intervals:
    if s &gt;= last_end:
        chosen.append((s, e)); last_end = e

Open the interactive Interval Scheduling visualisation →