Good data structure for finding date intervals including a given date

[Emile van Sebille]

On 5/12/2012 5:17 AM Jean-Daniel said...
> Hello,
>
> I have a long list of n date intervals that gets added or suppressed
> intervals regularly. I am looking for a fast way to find the intervals
> containing a given date, without having to check all intervals (less
> than O(n)).

ISTM the fastest way is to retrieve the list of intervals from a dict 
using the date as a key.  You don't say how long your list of intervals 
is, nor how large each interval can be so I don't have enough info to 
determine the setup reqs, but I'd suspect that a list of tens of 
thousands of intervals covering ranges of days to weeks would be doable. 
  If instead you're talking about millions of ranges covering years to 
decades I'd start elsewhere.

Emile