Overview
Disjoint interval structures maintain a set of non-overlapping ranges under insertions and removals, merging or splitting ranges as needed. Instead of processing a static list once (see Intervals), they answer online queries: add a range, remove a range, and ask whether a point or range is covered.
The standard implementation is an ordered map from start to end (Java TreeMap). To add [l, r], find all stored intervals that overlap or touch it, remove them, and insert one merged interval. Each interval is inserted and removed at most once, so operations are O(log n) amortized.
Each time someone paints a stretch of fence, you record painted sections. If the new stretch touches or overlaps existing ones, you merge them into one longer painted section, so your notebook always lists separate, non-overlapping painted parts.
When to use it
- A stream of numbers or ranges must be summarized as disjoint intervals.
- Range coverage queries with inserts and deletes (range module).
- Booking systems that must reject overlapping reservations.
- Counting total covered length as ranges are added.
Problem patterns it solves
Recognize it when: add numbers one by one and report current ranges.
- 352. Data Stream as Disjoint Intervals
- 228. Summary Ranges
Recognize it when: track which parts of a number line are covered.
- 715. Range Module
- 2276. Count Integers in Intervals
Recognize it when: accept a booking only if it does not overlap.
- 729. My Calendar I
- 731. My Calendar II
- 732. My Calendar III
Recognize it when: report ranges not covered.
- 163. Missing Ranges
- 759. Employee Free Time
Where it is used in real software
Free-space managers keep disjoint free ranges and merge neighbors when memory is released (coalescing).
Track which byte ranges of a file have been downloaded, merging adjacent ranges.
Allocated address ranges are stored as disjoint intervals to find free blocks quickly.
Media players track buffered time ranges (the HTML5 TimeRanges API) as disjoint intervals.
Key terms
- Ordered map
- TreeMap (Java) keeps starts sorted and supports floor and ceiling.
- Merge on insert
- Absorb every interval that overlaps or touches the new one.
- Split on remove
- Removing [l, r) from [a, b) may leave [a, l) and [r, b).
- Amortized O(log n)
- Each stored interval is created once and deleted once.
How it works, step by step
- 1Find the left neighbor
floorKey(l): the interval starting at or before l. If it reaches l, extend l to its start.
- 2Absorb overlapping intervals
While the next interval starts at or before r, extend r to max(r, its end) and remove it.
- 3Insert the merged interval
put(l, r).
- 4Query coverage
floorEntry(l) covers [l, r) if its end >= r.
- 5Remove
Trim or split every interval overlapping [l, r).
Data Stream as Disjoint Intervals
Add 1, 3, 7, 2, 6 in order
| Add | Neighbors | Action | Intervals |
|---|---|---|---|
| 1 | none | new [1, 1] | [1,1] |
| 3 | none adjacent | new [3, 3] | [1,1] [3,3] |
| 7 | none adjacent | new [7, 7] | [1,1] [3,3] [7,7] |
| 2 | [1,1] ends at 1, [3,3] starts at 3 | merge both | [1,3] [7,7] |
| 6 | [7,7] starts at 7 | extend to [6, 7] | [1,3] [6,7] |
NOWAdd: 1 | Neighbors: none | Action: new [1, 1] | Intervals: [1,1]
Adding 2 bridged two intervals into one. The map always holds disjoint sorted intervals, so getIntervals is a simple iteration.
Implementation
// Sorted array of [start, end] with binary search: fine for moderate sizesclass SummaryRanges { constructor() { this.intervals = []; } addNum(value) { const list = this.intervals; let lo = 0, hi = list.length; while (lo < hi) { // first interval with start > value const mid = (lo + hi) >> 1; if (list[mid][0] <= value) lo = mid + 1; else hi = mid; } const left = list[lo - 1], right = list[lo]; if (left && left[1] >= value) return; // already covered const joinLeft = left && left[1] === value - 1; const joinRight = right && right[0] === value + 1; if (joinLeft && joinRight) { left[1] = right[1]; list.splice(lo, 1); } else if (joinLeft) left[1] = value; else if (joinRight) right[0] = value; else list.splice(lo, 0, [value, value]); } getIntervals() { return this.intervals.map((i) => [...i]); }}Complexity and performance
Each interval inserted and removed once.
One floor lookup.
splice shifts elements.
In-order iteration.
Trade-offs
A sorted array with binary search is simple and cache-friendly, but inserts are O(n). A balanced tree keeps all operations O(log n).
Half-open [l, r) makes adjacency and lengths (r - l) simpler; closed intervals need +1 adjustments when merging neighbors.
Variants and related techniques
For coverage counts with huge coordinates, use a dynamic segment tree with lazy assignment.
Stores possibly overlapping intervals and answers 'which intervals contain point x?'.
If all ranges are known in advance, sort and merge once instead of maintaining a live structure.
Common mistakes
- Forgetting adjacency merges.
Fix: With integers, [1, 3] and [4, 6] should merge into [1, 6] in summary-range problems.
- Modifying a map while iterating with a stale entry.
Fix: Re-query ceilingKey or floorEntry after each removal.
- Mixing closed and half-open conventions.
Fix: Pick one and convert inputs at the API boundary.
Interview questions
Why is adding a range amortized O(log n)?
Each stored interval is removed at most once after it is inserted, so the total number of removals across all operations is bounded by the number of insertions. Each map operation is O(log n).
How would you implement this in JavaScript, which lacks TreeMap?
Use a sorted array with binary search for moderate sizes, or implement a balanced tree / skip list. Mention the O(n) insert cost of array splicing.
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| 228. Summary Ranges | Easy | Static grouping. |
| 729. My Calendar I | Medium | Overlap rejection. |
| 352. Data Stream as Disjoint Intervals | Hard | Merge neighbors on insert. |
| 715. Range Module | Hard | Add, remove, query. |
| 2276. Count Integers in Intervals | Hard | Maintain covered count. |