Interval problems show up in real systems all the time — calendar scheduling, rate limiting, range locks, time-series query planning. The tricks generalize.
The two go-to moves
1. Sort by start, sweep. Most “merge / overlap / non-overlap” questions collapse once you sort by start time and process in order. Maintain “current end”; for each next interval, either extend or emit-and-reset.
2. Separate starts and ends, sweep both. For “minimum rooms” / “max concurrent” / “first available” — split intervals into start and end events, sort each, walk a counter. The count = active intervals at any moment.
Canonical problems and their shape
| Problem | Approach |
|---|---|
| Merge overlapping intervals | Sort by start; walk; extend prev.end = max(prev.end, cur.end) if overlap |
| Non-overlapping intervals to remove | Sort by end; greedy keep, drop any whose start < kept end |
| Minimum meeting rooms | Sort starts and ends separately; two-pointer; counter goes up on start, down on end; track max |
| Insert interval into sorted set | Three phases: before, overlapping (merge), after |
| Employee free time | Multi-source merge of k schedules → free time is the gap |
Sweep line, generalized
For 2D / time-window problems where multiple events change state at known times:
- Generate all events
(time, type, payload). - Sort by time (ties broken so that “starts” come before “ends” — or after, depending on whether you treat boundaries as inclusive).
- Walk events, maintain active state (counter, set, segment tree).
This is what query optimizers, analytic engines, and time-series databases do internally.
Boundary conventions matter
[start, end) half-open vs [start, end] closed: pick one and stay consistent. The “do these touch” question is a.end == b.start:
- Closed intervals: they overlap.
- Half-open: they don’t.
Half-open is friendlier for arithmetic (length is end - start, no off-by-one) and is what most APIs use under the hood. Closed is friendlier for human-readable schedules. Mixing them is the source of half your bugs.
When intervals get heavy
For very large or dynamic interval sets:
- Interval tree / segment tree —
O(log n)queries for “any interval covering point X” or “all intervals overlapping range”. - Skip list of intervals — for ordered range queries with concurrent inserts.
- R-tree — for 2D+.
For app-level scheduling code (handfuls to thousands of intervals), sort+sweep is plenty.