Intervals
Ranges with a start and end — sorting by start (or end) turns overlap and merge problems into a single linear pass.
What it is
An interval is a [start, end] range. Most interval problems (merge overlapping ranges, insert a new interval, find the minimum number of rooms needed) become a single linear scan once the intervals are sorted correctly.
The core trick
Sort by start time. Then two intervals overlap exactly when the next interval's start is ≤ the current interval's end — no need to compare every pair, just adjacent ones in sorted order.
Common patterns
- Merge overlapping intervals — sort by start, then walk through merging into the last kept interval whenever they overlap.
- Minimum meeting rooms — sort start and end times separately; a two-pointer scan tracks how many meetings are simultaneously active.
Complexity
Sorting is O(n log n); the scan afterward is O(n) — so the whole thing is O(n log n), dominated by the sort.
Why sliding window comes first
Both techniques scan a sequence left-to-right maintaining a "currently active" state — intervals just add the sort-first step to make that scan valid.