Intro

You have a set of intervals: meeting times, date ranges, or segments on a number line. Now you need to answer: which intervals contain a given point?

Which intervals overlap with a query range? Scanning all $n$ intervals takes $O(n)$ per query. With thousands of intervals and thousands of queries, that's too slow.

Interval trees solve this. They organize intervals so you can find all $k$ overlapping intervals in $O(\log n + k)$ time.

The $\log n$ finds where to look; the $+k$ is unavoidable since you must report each result.

In this section, I'll show you how interval trees work, how to build them, and how to query them. You'll apply these to scheduling problems, range stabbing queries, and overlapping interval detection.