Efficiently finding overlapping intervals from a list of intervals

Question

This is related to finding overlapping intervals. I know how to do so given a list of intervals (interval trees). What I have is a list of list of intervals. For example,

[2,6], [7,11]
[1,3], [5,10], [11,13]
[2,5], [6,8]

The result for this should be

[2,3], [7,8]

What I need to do is to find a list of intervals that are common in all the lists.

I see this problem as similar to merging n lists. The problem is I cannot apply pairwise merging of lists. Applying this method can cause a loss of overlapping intervals. So I need to merge all the lists together considering all of them at a time (instead of pairwise).

I can use interval trees. Inserting the first intervals from each list to the interval tree and finding the overlap. Removing the weakest interval from the tree and inserting next interval from one of the lists. I haven't yet completely figured out how I can use this method but it seems It'll get too expensive.

Is there any efficient algorithm for finding overlapping intervals from a list of list of intervals.?

Additional Info: The intervals within a list are sorted. They don't overlap and form a sequence.

Answer 1

Create a single, sorted array of transitions. Each transition has a position, and a cumulative number based on how many intervals you're joining or leaving. As you pass through the list, keep track of how many intervals you are in. When you're in as many intervals as series, that's when you're in a common interval.

For your example the transitions would be:

[2, 1], [6, -1], [7, 1], [11, -1],
[1, 1], [3, -1], [5, 1], [10, -1], [11, 1], [13, -1]
[2, 1], [5, -1], [6, 1], [8, -1]

which after sorting by position and merging collapses to:

[1, 1], [2, 2], [3, -1], [5, 0], [6, 0], [7, 1], [8, -1], [10, -1], [11, 0], [13, -1]

which gives you transitions for running totals of:

[1, 1], [2, 3], [3, 2], [7, 3], [8, 2], [10, 2], [13, 1]

And then we can read off the intervals where we're at 3 as one starting at 2 and going to 3, and another starting at 7 and going to 8. Which is the answer.

The idea of creating one long list and sorting is admittedly extra work. You can instead create those lists and merge them on the fly. The savings is a factor of the log of the number of series rather than the log of the number of events.

Answer 2

My understanding of what you want to do is to apply the intersection operation over list of intervals. And you can do this pairwise as intersection is associative.

What I would do is something like

Let S be the set of sets, R = s1, s1 in S
     for each set s2 in S / {s1}
              for each element e1 in R
                  for each element e2 in s2 s.t. e1.sup < e2.inf
                    e1 <- intersection (e1, e2)

And the intersection operation between two intervals is

 intersection (e1,e2):
    return new Interval(max(e1.inf, e2.inf), min (e1.sup, e2.sup));

Answer 3

You said each individual list of intervals is sorted and non-overlapping. So,

Keep track of where you are in each list, starting at the beginning of each.
While none of the lists has run out:
    If the current intervals (one from each list) all overlap:
       Output the intersection of the current intervals
    Find which of the current intervals has the earliest end point
    Advance one position within that list.

If there are K lists of intervals and N intervals altogether, this should take O(N K) time if implemented in the most straightforward way, but you should be able to reduce this to O(N log K) time by tracking information about the current intervals in a heap or some other priority queue.