Given two sorted lists of intervals, return the overlapping intervals between the two lists

You are given two lists of intervals, A and B.

In A, the intervals are sorted by their starting points. None of the intervals within A overlap.

Likewise, in B, the intervals are sorted by their starting points. None of the intervals within B overlap.

Return the intervals that overlap between the two lists.

Example:

A: {[0,4], [7,12]}
B: {[1,3], [5,8], [9,11]}

Return:

{[1,3], [7,8], [9,11]} 

I got this in an interview and was stumped.

I thought of comparing intervals between the two lists. If there is an overlap between the two, add the overlap to a results list. I then advance the pointer of the list with the smaller starting interval but was unable to get to a working solution by the end of the interview.

What is the best way to solve this problem?

Here is an implementation, following the roman principle divide-et-impera:

First, find a method, which, for a given pair of Intervals, finds the overlap, if any.

/* Cases: A behind B, A overlap at start, A part of B, B part of A,
   overlap at end, B starts after A ended:
A:    2..3..4..5
Bs:   |        | 
0..1  |        |
0..1..2..3     |
0..1..2..3..4..5..6
      |  3..4  |
      |     4..5..6
      |        |  6..7
*/
case class Interval (lower: Int, upper: Int) {
    def overlap (other: Interval) : Option [Interval] = {
        if (lower > other.upper || upper < other.lower) None else 
        Some (Interval (Math.max (lower, other.lower), Math.min (upper, other.upper)))
    }
}

That was the method with a limited responsibility, to decide for two Intervals.

If you're not familiar with Scala: Interval is a class, and the first line can be read as constructor. Lower and upper should be self explaining (of type Int). The class has a method overlap, which takes a second instance of the class (other) and returns, as a result, a new Interval of the overlapping. But wrapped into an Option, which means: If no overlap is found, we return None. If we find one, it is Some (Interval). You can help yourself to understand this construct as a List, which is either empty, or contains exactly one element. It's a technique to avoid NullpointerException, by signalling, that there might be no result, with a Type.

If the upper of the one Interval is lower than the lower of the other interval, there can't be an overlap, so we return None.

For the overlap, we take the maximum of the two lower bounds as lower bound, and the minimum of the two upper bounds, as new upper bound.

Data:

val a = List (Interval (0, 4), Interval (7, 12))
val b = List (Interval (1, 3), Interval (5, 8), Interval (9, 11))

Naive approach: Bubble overlap (first make it work, then make it fast):

scala> a.map (aa => b.map (bb => aa.overlap (bb))).flatten.flatten
res21: List[Interval] = List(Interval(1,3), Interval(7,8), Interval(9,11))

The core, if you're not used to Option/Maybe with Some(T) and None, which might help to understand, is:

a.map (aa => b.map (bb => aa.overlap (bb))) 
res19: List[List[Option[Interval]]] = List(List(Some(Interval(1,3)), None, None), List(None, Some(Interval(7,8)), Some(Interval(9,11))))

The first flatten combined the two inner Lists into one List, and the second flatten removed the Nones and left us with Intervals, instead of the wrapper Some(Interval).

Maybe I can come up with an iterative solution, which takes no interval more than 2 times more often, than it matches. ...(10 min later)... Here it is:

def findOverlaps (l1: List[Interval], l2: List[Interval]): List[Option[Interval]] = (l1, l2) match {
    case (_, Nil) => Nil 
    case (Nil, _) => Nil
    case (a :: as, b :: bs) => {
             if (a.lower > b.upper) findOverlaps (l1, bs) 
        else if (a.upper < b.lower) findOverlaps (as, l2) 
        else if (a.upper > b.upper) a.overlap (b) :: findOverlaps (l1, bs) 
        else                        a.overlap (b) :: findOverlaps (as, l2) 
    }
}

The first two inner lines check, if either of the Lists is empty - then no more overlap can be expected.

(a :: as, b :: bs) is a match of (l1, l2) a is the head of l1, as the tail of l1 (might be Nil) and analog b is the head of l2, bs its tail.

If a.lower is > b.upper, we take the tail of the b list and repeat recursively with the whole l1-list and similar, with the whole l2-List but only the tail of the l1 list, if b.lower > a.upper.

Else we should have an overlap so we take a.overlap (b) in either case, with the whole list of the one with higher upper bound, and the tail of the other list.

scala> findOverlaps (a, b)
res0: List[Option[Interval]] = List(Some(Interval(1,3)), Some(Interval(7,8)), Some(Interval(9,11)))

You see, no None was generated, and for findOverlaps (b, a) the same result.