Good data structure for finding date intervals including a given date

[Karl Knechtel]

On Sat, May 12, 2012 at 10:18 AM, Jean-Daniel
<jeandaniel.browne at gmail.com> wrote:
>> Since you say "intervals" in plural here, I assume that they can overlap?
>
> Yes,
>
> For instance, there are the following intervals :
> [[1, 10],
> [4, 7],
> [6, 15],
> [11, 17]]
>
> asking for the intervals including  5, the returned value should be
>
> [[1, 10],
> [4, 7]]
>
> The idea here to make it fast is to have done some preprocessing at
> insertion time, so that not all intervals are processed at query time.
>

How about this:

Set up a list of lists of intervals. Insert the intervals one at a
time thus: for each existing list, check if the new interval overlaps
any existing intervals - you can use the `bisect` module to check for
where the new interval would "fit". If there is no overlap, insert it
into that list at the discovered "insertion point"; otherwise move on
to the next list. If no lists are found that can hold the new
interval, append a new list for it.

Then at query time, you just iterate over the lists, using `bisect`
again to find the unique interval (if any) in each list that spans the
specified point in time.

-- 
~Zahlman {:>