1-D Interval Intersection

Suppose we have \(N\) 1-D intervals of the form \((a,b)\) where \(a<b\). For convenience, let’s assume no two intervals share an endpoint.

Now given an interval \((x,y)\), we want to see if it intersects with any interval in our list.

The way to do this is to build a binary search tree with the left endpoints as the keys. In each node, we store the maximum of the right endpoints in the subtree.

The algorithm is:

1. If interval in the current node intersects \((x,y)\), we’re done.
2. If the left subtree is empty, go to the right subtree.
3. If the maximum endpoint in the left subtree is smaller than \(x\), go to the right subtree. Otherwise, go to the left subtree.