Interval Trees: Finding Every Overlapping Time Range Instantly

The Overlap Problem and Why Brute Force Struggles

An interval is simply a range with a start and an end, such as a meeting from 2pm to 3pm, a genomic region spanning certain base-pair positions, or a segment along a line in a geometric model. The core question an interval tree answers is: given a query interval or a single point, which of the stored intervals overlap it? This sounds simple, and for a small handful of intervals it is. The naive approach is to walk through every single stored interval, one by one, and check whether it overlaps the query. That takes time proportional to the total number of intervals, written n in prose, for every single query, because there is no shortcut: each interval must be individually inspected regardless of how the data is arranged in memory. If a calendar system stores thousands of appointments and needs to check for conflicts every time a new meeting is proposed, or a bioinformatics tool needs to repeatedly query millions of genomic features, this linear-time-per-query cost becomes a serious bottleneck. The inefficiency is not that any single check is expensive, it is that there is no way to rule out large groups of intervals at once. Brute force treats every interval as equally worth checking, even when most of them are nowhere near the query. This is exactly the situation where a smarter, search-tree-based structure pays off, because it can eliminate whole groups of candidates without examining them individually.

Augmenting a Binary Search Tree with Max Endpoints

An interval tree starts from something familiar: a standard binary search tree. Each node holds one interval, and the tree is ordered by the interval's starting point, exactly like an ordinary BST is ordered by a single key. This alone would let you quickly find intervals with a particular start, but it would not help you find overlaps, since two intervals can overlap even when their starting points are far apart in the ordering. The key trick is augmentation: every node is additionally tagged with the maximum endpoint found anywhere in its entire subtree, not just its own interval's endpoint. This means a node near the root might store a modest interval of its own, but its max-endpoint annotation could reflect a much longer interval buried deep among its descendants. Maintaining this annotation is cheap. Whenever a node is inserted or removed, the max-endpoint values along the affected path can be recomputed by comparing a node's own endpoint against the max-endpoint values of its two children and taking the largest of the three. This one extra number per node is what transforms a plain binary search tree into a structure capable of answering overlap queries efficiently, because it summarizes, at a glance, whether it is even worth descending into a subtree at all.

Pruning: Skipping Subtrees That Cannot Possibly Overlap

The max-endpoint annotation earns its keep during search. When looking for intervals that overlap a query, the algorithm walks the tree starting at the root, and at each node it makes a decision about whether to explore the left subtree, the right subtree, both, or neither. The crucial pruning rule is this: if a subtree's maximum endpoint is less than the query's start point, then absolutely no interval anywhere in that subtree can possibly overlap the query, because every interval in that subtree ends before the query even begins. The entire subtree, no matter how large, can be skipped in a single comparison, without visiting a single one of its nodes. This is fundamentally different from brute force, where every interval must be individually examined. Here, one glance at an annotation can eliminate thousands of intervals at once. At each node the algorithm also checks whether the current node's own interval overlaps the query, and reports it if so, before deciding which children are worth visiting based on their start points and max-endpoint values. The combination of the BST ordering by start point and the max-endpoint pruning rule means the search only ever explores the parts of the tree that could plausibly contain a match. Everything else is discarded early, which is exactly what makes the structure fast even as the number of stored intervals grows very large.

Query Time: Logarithmic Search Plus the Matches Found

Because the interval tree is built on a balanced binary search tree, its height is proportional to the logarithm of the number of stored intervals, written log n in prose. Descending from the root to a leaf, making pruning decisions along the way, takes time proportional to that height. On top of this traversal cost, the algorithm also needs time to report each overlapping interval it actually finds, since every match must be visited and returned to the caller. Putting these two pieces together, the total query time is proportional to log n plus the number of overlaps actually found. This is a dramatic improvement over the brute-force cost of checking all n intervals for every query, especially when the query set is large but the number of actual overlaps for a typical query is small. Even when many overlaps exist and must all be reported, the tree still avoids wasting any effort on the vast majority of stored intervals that share no relationship with the query at all. Insertion and deletion also run in time proportional to log n, since they only need to update the max-endpoint annotations along a single root-to-leaf path, making the interval tree a practical choice not just for static collections but for interval sets that change frequently, such as a calendar where meetings are constantly being added, moved, and cancelled.

A Worked Example and Real-World Applications

Picture six intervals stored in a tree ordered by start point: (15,20), (10,30), (17,19), (5,11), (4,8), and (21,23). The tree keeps the max-endpoint annotation at each node, so the root covering (15,20) might show a subtree max endpoint of 30, reflecting the (10,30) interval nested beneath it. Suppose the query is the point 22. Starting at the root, the search checks whether (15,20) overlaps 22, it does not, then looks at the left and right children. If a child's subtree max endpoint is less than 22, that whole branch is pruned instantly. Following the branch containing (10,30) and (21,23), the search finds that (21,23) overlaps 22 and reports it, while branches rooted at intervals like (4,8) get skipped the moment their max endpoint, 8, is compared against the query point and found too small to matter. Only a handful of nodes are ever visited, not all six. This same pattern scales up dramatically in practice. Calendar and scheduling software uses interval trees to instantly detect booking conflicts among thousands of appointments. Bioinformatics tools rely on them to find every gene, exon, or regulatory region that overlaps a newly sequenced genomic segment among millions of annotated features. Computational geometry algorithms use interval trees to detect overlapping segments or bounding boxes efficiently, which is essential for collision detection and spatial indexing in graphics and simulation systems.

Frequently asked questions

Try it live

Everything above runs in your browser — open Interval Trees: Finding Every Overlapping Time Range Instantly and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.