Given set of intervals sorted according to Start time. Count all the intervals which has Time "T" in them in O(logn)

Question

Suppose the list of intervals may be [[1,3],[2,4],[6,12]] and the Query time T = 3. The number of intervals which have 3 in the above list are 2 (i.e) [[1,3],[2,4]]. Is it possible to do this in O(logn) time?

Answer 1

This cannot be done in O(log n) time in the general case.

You can binary search on the start time to find the last interval that could possibly contain the query time, but because there's no implied ordering on the end times, you have sequentially search from the start of the list to the item you identified as the last to determine if the query time is in any of those intervals.

Consider, for example, [(1,7),(2,11),(3,8),(4,5),(6,10),(7,9)], with a query time of 7.

Binary search on the start time will tell you that all of the intervals could contain the query time. But because the ending times are not in any particular order, you can't do a binary search on them. You have to look at each individual interval to determine if the ending time is greater than or equal to the query time. Here, you see that (4,5) does not contain the query time.

Answer 2

Let's take your assumption that the intervals are sorted by start time. A binary search O(log n) will eliminate the intervals that can't contain T. The remaining might.

Assuming End Time is not also Sorted (OP)

You have to scan the remaining ones, O(n), counting them. Total complexity O(n). Given this, you might as well have never binary searched and just scanned the whole list.

Assuming End Time is also Sorted

If the remaining ones are sorted by end time as well, you can do another binary search, keeping the complexity at O(log n).

But you're not done. You need the count.

You know the count to start with. If you didn't you couldn't have binary searched. You will know the indexes of the last tests of each binary search. From here it's an O(1) calculation option.

Thus the total complexity is O(log n) for this option.

Answer 3

Well, one thing to note is that for an interval to contain T, its start time must be less than or equal to T. Since these are sorted by start time, you can use a basic binary search to eliminate all the ones which start too late in O(log n) time.

If we can assume that these are also sorted by end time -- that is, no interval completely encompasses a previous interval -- then you can use another binary search to eliminate all the ones whose end times are before T. That will keep the running time in O(log n).

If we can't make that assumption, things get more complex, and I can't think of any way to do better than O(n log n) [by sorting the remaining list by end time and performing another binary search on that]. Perhaps there's a way?

EDIT As Qbyte says below, the final sort is superfluous; you can get it down to O(n) with a simple linear search on the remaining set. Then again, if you're going with an O(n) solution anyway, you may as well skip the entire algorithm and just do a linear search on the original set.