Good data structure for finding date intervals including a given date

[Christian Heimes]

Am 12.05.2012 14:17, schrieb Jean-Daniel:
> 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)).
> 
> Do you know the best way to do this in Python with the stdlib?
> 
> A variant of the red black trees can do the job quickly [1], is this a
> good enough use case to discuss the inclusion of a red black tree
> implementation in the stdlib?

A more general data structure for spatial search are R-Trees [1]. In few
words R-Tree optimize indexing and containment tests in n dimensions.

Christian

[1] http://en.wikipedia.org/wiki/R-tree