Interval basics
An interval [start, end] is every value from start to end, both ends included. Every interval
question comes down to how two of them sit on the number line. Pick a chapter: one interval, two separate
ones, the shapes of an overlap, merging two, their common part, and merging many after sorting by start.
Each bar is a range, the axis under it is the number line; a green band is a stretch both share, a red one
a gap that belongs to neither. The code is one reusable Range class.
The two checks behind every interval question
- Separate:
A.end < B.start(A is behind B) orA.start > B.end(A is ahead of B). - Overlap: not separate. Touching at one point counts, because both ends are included.
- Merge (only when they overlap):
[min(starts), max(ends)]. - Common part:
[max(starts), min(ends)], empty when its start is past its end.