Overlapping Intervals

Question

Assume that you are given a set of intervals (not necessarily integral in length). How do you determine if there is an overlap between any two intervals in the given set? I am wondering if there is a linear solution in the number of intervals.

P.S: Not a HW problem. This was asked in one of my interviews with a company.

Answer 1

If all the intervals are sorted by start point, then it's easy to check whether there is two of them overlap. Just scan through all the intervals, keep the maximum end point we got from previous intervals, and if the max end point > current start point, then we got a overlap. If we haven't get overlap for all intervals, then there is no overlap.

If the intervals are not sorted. Then in general the lower bound to detect overlap is O(n logn). Because when all intervals have start_point = end_point, then the problem is reduced to distinctness problem. http://en.wikipedia.org/wiki/Element_distinctness_problem. All comparison based algorithm need O(n log n) time.

However, if the points of all intervals are discrete and in some certain range [0,L), e.g. the seconds in a day is from 0 to 60*60*24, then it can be solved in O(n+L) linear time and O(L) space.

The idea is that, each interval i has a start point si and end point ei. We create an array a = new int[L]. For each interval i, we add 1 for a[si] to a[ei]. Then we check whether there is an a[j] > 1, if so we get an overlap.

The most naive method is using 2 for loops and the time complexity is O(n*L). In Programming Peals there is a clever algorithm which could reduce the running time to O(n+L). If you are interested and this is what your interviewer wants, I can show you the detail.

So, this is the 3 situations I know. Which one do you think fits your problem.

Answer 2

Look into the data structure called Interval Tree. This is used to find overlapping intervals.

If the intervals are sorted by their starting values, this is a simple problem in O(n).

An alternative would be to mark each interval in an array of size m and progressively check if they overlap. The size of the array (say m) can be determined in O(n), but the space and time requirement would be O(m).