Data structure for quick time interval look up
data-structures
Solution
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
Problem
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.