Ordered intervals (range module)
Keep disjoint sorted intervals; add merges neighbours, remove splits them.
The stored intervals are disjoint and sorted at all times.
01The intuition
Start with what you would do by hand
A room-booking desk tracks which stretches of the day are taken. Someone books 10 to 20. Later the 14 to 16 part is cancelled. A caller asks whether 13 to 15 is fully booked: no, because 14 to 15 is free. Then 16 to 18 is booked again, and someone asks whether 16 to 19 is fully booked: yes.
By hand you might keep a mark for every minute of the day. That is fine for a day, and hopeless when times run to a billion. Keeping an unsorted pile of booked stretches is compact but every question has to read the whole pile, and overlapping stretches pile up until nobody can tell what is really booked.
Build the structure, one piece at a time
Piece one: represent a stretch as a half-open range [a, b), meaning a is included and b is not. This makes two ranges that touch, [10, 14) and [14, 16), cover exactly [10, 16) with no gap and no double count.
Piece two: keep the ranges in a list sorted by start, and never let two of them overlap or touch. The list after each operation:
| operation | stored ranges |
|---|---|
| add [10, 20) | [10, 20) |
| remove [14, 16) | [10, 14), [16, 20) |
| query [13, 15) | false, the range starting at or before 13 ends at 14 < 15 |
| add [16, 18) | [10, 14), [16, 20), it was already inside |
| query [16, 19) | true, [16, 20) contains it |
Piece three: the three operations as edits to that list.
- add [a, b): find every stored range that overlaps or touches [a, b). Replace all of them, together with the new one, by a single range from the smallest start to the largest end.
- remove [a, b): find every stored range that overlaps it. Delete them, and put back the pieces that stick out: a left piece [start, a) if start < a, and a right piece [b, end) if end > b.
- query [a, b): find the stored range with the largest start that is at most a. The answer is true exactly when it exists and its end is at least b.
"Find" is a binary search on the sorted starts. In a language with an ordered map or a sorted-list container the find, insert and delete are all built in.
Why it is correct
The invariant is that the stored ranges are sorted, disjoint and non-touching, and their union is exactly the set of booked points. Add merges every range that could overlap or touch the new one into a single range, so the union grows by exactly the new range and no two stored ranges overlap afterwards. Remove cuts exactly the removed points out of each affected range, keeping the leftover pieces, so the union shrinks by exactly the removed range. For query, because the stored ranges are disjoint, a point belongs to at most one of them; the range with the largest start at most a is the only one that can contain a, and because ranges do not touch, [a, b) is fully covered only if that single range reaches b.
Why it is fast
A query is one binary search, O(log n) for n stored ranges. Add and remove binary search for the first affected range and then handle each affected range once; a range that is merged or deleted disappears, so over the whole life of the structure each range is created once and removed at most once. Averaged over all operations, add and remove cost O(log n) each. The minute-by-minute marks cost time and memory proportional to the size of the timeline, not the number of bookings.
How to recognise it in an interview
Cues: "add a range", "remove a range", "is this interval fully covered", "book a time without double booking", "how many overlapping bookings". Say: "I will keep disjoint sorted intervals, merge on add, split on remove, and binary search on query".
Range Module is the structure above exactly. My Calendar I is the add operation with a check: before inserting, find the neighbours and refuse if either overlaps. Exam Room is the mirror image, storing the occupied seats in sorted order and binary searching for the largest gap between neighbours.
02The idea in one line
Keep disjoint sorted intervals; add merges neighbours, remove splits them.
Reach for it when: Range module, my calendar I/II/III, data stream disjoint intervals, exam room.
Cost: O(log n) per op.
03The walk-through, step by step
The video works one example: Range Module add [10,20), remove [14,16), query [13,15). These are its captions in order, so you can follow without the video or check a step you missed.
- Keep a sorted list of disjoint half-open ranges
- add [10,20): nothing overlaps, insert it
- remove [14,16): find ranges overlapping it
- Cut: keep the left piece [10,14) and the right piece [16,20)
- query [13,15): find the range starting at or before 13
- [10,14) ends at 14 < 15: not fully covered → false
- add [16,18): it overlaps [16,20)
- Merge overlapping neighbours into one range: still [16,20)
- query [16,19): inside [16,20) → true
- Binary search for the neighbours: O(log n) per op
04Asked at Google
7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Range Module | Hard | 40 | last 6 months |
| My Calendar I | Medium | 27 | |
| My Calendar II | Medium | 24 | |
| Exam Room | Medium | 21 | |
| My Calendar III | Hard | 20 | |
| Data Stream as Disjoint Intervals | Hard | 8 | |
| Count Integers in Intervals | Hard | 6 |
05Related patterns
Other patterns in Design: Hash map + doubly linked list (LRU), Hash map + array for O(1) random, Time-versioned map, Lazy iterators, Streaming data structures.