get the number of overlapping intervals, given two lists of intervals

Question

I recently came across an interesting problem:

Given two lists of intervals, find the total number of overlapping intervals from the two lists.

Example

L1: ([1,2][2,3][4,5][6,7])
L2: ([1,5][2,3][4,7][5,7])

[1,5] overlaps [1,2] [2,3] [4,5]
[2,3] overlaps [1,2] [2,3]
[4,7] overlaps [4,5] [6,7]
[5,7] overlaps [4,5] [6,7]

total = 3+2+2+2 = 9

Obviously the brute force approach works, but it's too slow (I need something better than O(n^2)).

I also fond a similar problem here. But it's not exactly the same...

Any help is appreciated

Answer 1

Make two sorted lists with pairs (value; +1 or -1 for start and end of interval).

Two counters - Count1 and Count2 which show number of active intervals in the first and the second lists.

Walk through both lists in merge manner.

When you get pair from the first list with +1 - increment Count1

When you get pair from the first list with -1 - decrement Count1 and add Count2 to the result

The same for pairs from the second list

Pseudocode for the last stage

CntA = 0
CntB = 0
Res = 0
ia = 0
ib = 0
while (ia < A.Length) and (ib < B.Length)
    if Compare(A[ia], B[ib]) <= 0
          CntA = CntA + A[ia].Flag
          if (A[ia].Flag < 0)
               Res = Res + CntB
          ia++
    else
          CntB = CntB + B[ib].Flag
          if B[ib].Flag < 0
             Res = Res + CntA
          ib++

Subtle moment - comparison if Compare(A[ia], B[ib]) <= 0 We should here take into account also flags - to correctly treat situations when endpoints only touch like [1..2][2..3] (you consider this situation as intersection). So both sorting and merge comparator should take synthetic value like this: 3 * A[ia].Value - A[ia].Flag. With such comparing start of interval is treated before end of interval with the same coordinate.

P.S. Made quick test in Delphi. Works for given data set and pair of others.

Delphi code (ideone FPC doesn't compile it due to generics)

Answer 2

Try to look for sweep line algorithms, it will give you the fastest solution.

You can check short description at TopCoder site or watch video from Robert Sedgwick. These describe a bit more hard problem but should give you an approach how to solve yours.

Actually the main idea is to walk over sorted list of begins and ends of your segments each time updating the lists of segments in the special intersecting list.

For this task you will have two intersections lists for each original list respectively. At the start both intersection lists are empty. On coming over begin of the segment you add it to the appropriate intersection list and it obviously intersects all the segments in the other intersection list. When coming to an end of the segment just remove it from the intersection list.

This algorithm will give you O(n log(n)) speed and in worst case O(n) memory.