Is there any more efficient algorithm to find all intervals containing a specific time?

user_5529197 0
Viewed 124

Let's assume that I have a sorted list of start_time and duration pair which is sorted based on start_time. I need to find all entries that cover a specific time. For example:

index start_time        duration
--------------------------------
1     2                   7
2     4                   1
3     5                   3
4     7                   4

find(6) = {1,3}

I can do this easily in O(n) by simply traversing through list. But I wonder if there is any algorithm or data structure to improve this time. Any idea?

algorithm
1 Answers

No. I write the array as (start_time, end_time) it's easier for us to reason that way. Consider [(1,100),(2,99),(3,96),(4,102)], with point 101.

What I did here is choose the lower bound of the target interval to be obviously included by the lower bounds of your list, so the fact that they are sorted is of little use here, you will know, in O(log(n)) if you wish, that all interval starts are valid. Interval ends are the question to be answered, and it is equivalent to the question of being given a number (101), an unsorted array (the interval end times, or alternatively the durations which are an implicit statement of the end-times), find all numbers that are larger than this number, which is only doable in O(n). An interval tree as suggested by one of the comments would help you in queries, but for a single point, you must read all the intervals at least once.

user_79434290
Related