Data structure for quick time interval look up

Question

I have a set of time intervals In = (an, bn). I need to run lots of look ups where I'm given a time t and need to quickly return the intervals that contain t, e.g., those intervals such that an <= t <= bn.

What is a good data structure or algorithm for this?

If it matters, in my case the an and bn are integers.

Answer 1

What you are looking for is an Interval Tree (which is a type of Range Tree).

These have logarithmic lookup time like other tree structures (e.g., RB trees), so you should see comparable performance to using something like a Java TreeMap or an STL map.

• Code for Red-black trees and interval trees from MIT
• There is a C++ implementation in the CGAL Library.
• Here's a C# Implementation

Answer 2

This is basically a space partitioning question. You have a large space with containers and a specific point in that space, what containers does it touch? A lot of games have to solve this problem, so it wouldn't be a bad idea to start there. Look for articles on "broad phase collision detection".

The simplest way to do this is to divide your number space into a constant number of pieces. Each piece knows which sets intersect with it, something that you calculate whenever a new set is added. Now, rather than testing every single set when you have a point, you only need to check the sets contained within the piece that the point is in.

Another general and efficient algorithm used is Binary Space Partioning. This algorithm subdivides your space into two sides. Each side would know which sets intersect with it. You can recursively repeat this process to your desired precision (although it doesn't make sense to ever create a subdivision smaller than the range of your smallest set).

Answer 3

You are welcome to check out the C# implementation I've posted on CodePlex for IntervalTree which solve this problem exactly.

Ido.