Data structure for quick time interval look up
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 … Read more