CODEWITHSUNDEEP
algorithmsearchtime-complexity
jacobhaven
jacobhaven

Reputation: 393

Time complexity of searching a list of intervals

Let a be an interval [a.start, a.end], where a.start and a.end are real numbers such that 0 <= a.start < a.end <= 1 .

Two such intervals a and b intersect if a.start < b.start < a.end OR b.start <= a.start < b.end

Let As be a sorted list of non-intersecting intervals a_0, a_1, ..., a_n such that a_i doesn't intersect a_j and a_i.start < a_j.start for i < j

Given the interval b, determine the first interval and last interval in As that b intersects (or find no intersections). i.e.: If possible, find i and j such that b intersects with a_i and a_j but not a_{i-1} or a_{j+1}

I've solved this with a modified binary search (O(n) in the worst case), so my intuition is that this is a lg(n) problem, but I don't know if I have the best algorithm.

Upvotes: 0

Views: 292

Answers (1)

mcdowella
mcdowella

Reputation: 19621

Because you have a sorted list of non-intersecting intervals, you know every interval ends before the next interval starts, and you can also regard this list as a sorted list of interval start points, or a sorted list of interval end points.

I think you can use binary search on a sorted list of interval end points to find the smallest interval end point which is at least as large as b.start in O(log n) worst case time, and this is the first interval that intersects b (if any interval intersects b). Similarly, the last interval that intersects b has the largest start point no larger than b.end, if any interval intersects b.

To find a smallest point at least as large as the target, look at the point in the middle of the range of possible solutions (by number of possible solutions, not by position). If this point is at least as large as the target, then the range of possible solutions extends from that point to the left, and includes that point. If this point is not at least as large as the target, the range of possible solutions extends from just after that point to the right. In either case you have reduced the number of possible solutions by about one half, so you have worst case O(log n).

Upvotes: 1

Related Questions