Possible Interview Question: How to Find All Overlapping Intervals

It's not an interview question per se, as I came across this in my project, but I figured it could be a decent intervew question.

You have N pairs of intervals, say integers. You're required to indentify all intervals that overlap with each other in O(N) time. For example, if you have

{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}

the answer is {1, 3}, {12, 14}, {2, 4}, {13, 15}. Note that you don't need to group them, so the result can be in any order like in the example.

I just threw in O(N) time because the KMP algorithm takes O(N) for string search. :D

The best I came up with and what I'm using right now in the project is O(N^2). Yeah, brute force is pretty sad, but no one complains so I won't refactor it. :P Still, I was curious if a greater mind has a more elegant solution.

Solution 1:

Throw the endpoints of the intervals into an array, marking them as either start- or end-points. Sort them by breaking ties by placing end-points before start-points if the intervals are closed, or the other way around if they're half-open.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E

Then iterate through the list, keeping track of how many intervals we're in (this equates to number of start-points processed minus number of end-points). Whenever we hit a start-point while we are already in an interval, this means we must have overlapping intervals.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
    ^                          ^
   overlap                    overlap

We can find which intervals overlap with which by storing data alongside the end-points, and keeping track of which intervals we're in.

This is an O(N logN) solution, with sorting being the main factor.

Solution 2:

Sort the intervals by start point. Then fold over this list, merging each interval with its neighbor (i.e. (1,4),(2,6) -> (1,6)) if they overlap. The resulting list contains those intervals with no overlapping partner. Filter these out of the original list.

This is linear in time after the initial sort operation which could be done with any (n log n) algorithm. Not sure how you'd get around that. Even the 'filter out duplicates' operation at the end is linear if you take advantage of the already-sorted order of the input and output of the first operation.

Here is an implementation in Haskell:

-- Given a list of intervals, select those which overlap with at least one other inteval in the set.
import Data.List

type Interval = (Integer, Integer)

overlap (a1,b1)(a2,b2) | b1 < a2 = False
                       | b2 < a1 = False
                       | otherwise = True
                                     
mergeIntervals (a1,b1)(a2,b2) = (min a1 a2, max b1 b2)
                                     
sortIntervals::[Interval]->[Interval]
sortIntervals = sortBy (\(a1,b1)(a2,b2)->(compare a1 a2))

sortedDifference::[Interval]->[Interval]->[Interval]
sortedDifference [] _ = []
sortedDifference x [] = x
sortedDifference (x:xs)(y:ys) | x == y = sortedDifference xs ys
                              | x < y  = x:(sortedDifference xs (y:ys))
                              | y < x  = sortedDifference (x:xs) ys

groupIntervals::[Interval]->[Interval]
groupIntervals = foldr couldCombine []
  where couldCombine next [] = [next]
        couldCombine next (x:xs) | overlap next x = (mergeIntervals x next):xs
                                 | otherwise = next:x:xs
                                               
findOverlapped::[Interval]->[Interval]
findOverlapped intervals = sortedDifference sorted (groupIntervals sorted)
  where sorted = sortIntervals intervals
                                     
sample = [(1,3),(12,14),(2,4),(13,15),(5,10)]