The Interval Pattern

Most interval problems follow this pattern:

$1.$ Sort: by start time (for merging) or end time (for selection)

$2.$ Scan: left to right, maintaining state

$3.$ Decide: at each interval: merge, extend, or start new

Without sorting first, you would need $O(n^2)$ comparisons to check all pairs. Sorting lets you process intervals in order, making local decisions that lead to global optimality. The pattern runs in $O(n \log n)$ time (sorting) and typically $O(1)$ space if done in-place.