L
lemmi
Hi,
I was wondering if someone of you could help me out with an
algorithmic problem I have. This is not a homework exercise but
something I need for a UI framework that I have developed
(www.dlsc.com).
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.
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).
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).
To make things complicated. The intervals can overlap each other. An
interval A that starts earlier than B might very well end after B.
A.start < B.start && A.end > B.end.
Note: a standard binary search does not work because it might find a
time interval that ends before the input time span TS and then
interrupts its search even though another time interval is located
before it that ends after it.
Dirk
I was wondering if someone of you could help me out with an
algorithmic problem I have. This is not a homework exercise but
something I need for a UI framework that I have developed
(www.dlsc.com).
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.
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).
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).
To make things complicated. The intervals can overlap each other. An
interval A that starts earlier than B might very well end after B.
A.start < B.start && A.end > B.end.
Note: a standard binary search does not work because it might find a
time interval that ends before the input time span TS and then
interrupts its search even though another time interval is located
before it that ends after it.
Dirk