Algorithms / Intervals On Lines
Least You Need to Know: Intervals on Lines, Overlap Tests, and Merge Reasoning
A large class of interview problems is really one-dimensional geometry in disguise. Once you model each object as an interval, the key moves are overlap tests, sorting by start point, and carrying the rightmost covered endpoint as an invariant.
The least you need to know
- Two closed intervals overlap when the larger start is at most the smaller end.
- Sorting intervals by start coordinate is the standard setup for merging or scanning coverage.
- A current merged interval is summarized by its rightmost covered endpoint.
- Whether touching endpoints count as overlap depends on closed versus half-open conventions.
- The union length or merged list is built by extending coverage only when the next interval reaches beyond the current end.
Key notation
[l, r]
closed interval from `l` to `r` inclusive
max(l1, l2)
later starting point
min(r1, r2)
earlier ending point
Tiny worked example
- For intervals `[1, 4]` and `[3, 6]`, the later start is `3` and the earlier end is `4`, so they overlap.
- After sorting by start, you can merge them into `[1, 6]` because the second start is inside the current covered range.
Common mistakes
- Many mistakes come from mixing closed intervals with half-open scheduling intervals.
- After sorting, the current right endpoint is the only history you usually need for simple merging.
- Overlap is a geometry condition on endpoints, not a question about lengths alone.
How to recognize this kind of problem
- The prompt mentions meeting slots, booking windows, time ranges, or covered segments on one axis.
- A sort-then-scan solution is expected and nested pairwise comparisons look wasteful.
- You need to decide whether two ranges interact, merge, or leave a gap.