Merge two sorted lists of intervals

Question

Given A and B, which are two interval lists. A has no overlap inside A and B has no overlap inside B. In A, the intervals are sorted by their starting points. In B, the intervals are sorted by their starting points. How do you merge the two interval lists and output the result with no overlap?

One method is to concatenate the two lists, sort by the starting point, and apply merge intervals as discussed at https://www.geeksforgeeks.org/merging-intervals/. Is there a more efficient method?

Here is an example:

A: [1,5], [10,14], [16,18]
B: [2,6], [8,10], [11,20]

The output:

[1,6], [8, 20]

Answer 1

Here is a different approach, in the spirit of the answer to the question of overlaps.

<!--code lang=scala--> 
def findUnite (l1: List[Interval], l2: List[Interval]): List[Interval] = (l1, l2) match {
    case (Nil, Nil) => Nil
    case (as, Nil)  => as
    case (Nil, bs)  => bs
    case (a :: as, b :: bs) => {
             if (a.lower > b.upper) b :: findUnite (l1, bs)
        else if (a.upper < b.lower) a :: findUnite (as, l2)
        else if (a.upper > b.upper) findUnite (a.union (b).get :: as, bs)
        else                        findUnite (as, a.union (b).get :: bs)
    }
}

If both lists are empty - return the empty list. If only one is empty, return the other. If the upper bound of one list is below the lower bound of the other, there is no unification possible, so return the other and proceed with the rest. If they overlap, don't return, but call the method recursively, the unification on the side of the more far reaching interval and without the consumed less far reaching interval.

The union method looks similar to the one which does the overlap:

<!--code scala--> 
case class Interval (lower: Int, upper: Int) {
    // from former question, to compare
    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)))
    }

    def union (other: Interval) : Option [Interval] = {
        if (lower > other.upper || upper < other.lower) None else
        Some (Interval (Math.min (lower, other.lower), Math.max (upper, other.upper)))
    }    
}

The test for non overlap is the same. But min and max have changed places.

So for (2, 4) (3, 5) the overlap is (3, 4), the union is (2, 5).

lower   upper
_____________
    2    4 
    3    5 
_____________
min 2    4 
max 3    5 

Table of min/max lower/upper.

<!--code lang='scala'--> 
val e = List (Interval (0, 4), Interval (7, 12))
val f = List (Interval (1, 3), Interval (6, 8), Interval (9, 11))
findUnite (e, f)
// res3: List[Interval] = List(Interval(0,4), Interval(6,12))

Now for the tricky or unclear case from above:

val e = List (Interval (0, 4), Interval (7, 12))
val f = List (Interval (1, 3), Interval (5, 8), Interval (9, 11))
findUnite (e, f)
// res6: List[Interval] = List(Interval(0,4), Interval(5,12))

0-4 and 5-8 don't overlap, so they form two different results which don't get merged.