Re: Need efficient search strategy in list of time intervals

lemmi <dlemmermann@xxxxxxxxx> writes:

I have a list of time intervals ([long,long]). The list is sorted
based on the start times of the intervals. I now need a fast
algorithm, which takes a time span TS as input and returns the index
of the first time interval A in the list that is contained in the
given time span. The rendering engine of my UI framework will then
iterate over the list starting at the calculated index.

Why iterate? The next element can't be assumed to be hit by TS, so you
might have to iterate over a long list of irrelevant objects anyway.

A time interval A is "contained" when A does not end before TS begins
and also does not start after TS ends (!(A.end < TS.start || A.start >
TS.end).

This is equivalent to (A.end >= TS.start && A.start <= TS.end).
I expect that A.start <= A.end (and likewise for TS) can be assumed.

That sounds like "overlaps", not "contained in". Example;
TS = [2,4]
A = [1,3]
satisfies the requirement.

The algorithm gets constantly called as part of a paint() method so it
needs to be extremely fast (linear is not good enough, logarithmic
would be ideal).

Sounds unlikely, at least in the worst case, since the end-points are
completely unordered. Worst case, assume a (long) list with same start
time, and only one interval has a large enough end time to overlap the
TS.

You should consider whether there is a better data structure than a list
for your purpose, to account for both start and end time.
I can't think of a one, but why think when you can google (for "time interval
data structure"). It seems an Interval Tree is what you need:
<URL:http://en.wikipedia.org/wiki/Interval_tree>.
Found this too:
<URL:http://i11www.iti.uni-karlsruhe.de/~awolff/map-labeling/design/old/interfaces/gen_interval_tree.ps>

Good luck
/L
--
Lasse Reichstein Nielsen - lrn@xxxxxxxxxx
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
.

Relevant Pages