# Intersection of lists of disjoint intervals

Here is my problem: I have two very large lists of intervals (stored as many couples in the form {{"start point", "end point"}, ..., {"start point", "end point"}), and I want the result of the intersection of those lists.

Here is an example :

intervalsA = {{1, 2}, {3, 4}, {5, 7}, {8, 8.5}};
intervalsB = {{1.5, 3.5}, {4.1, 6}, {9, 10}};


The expected result is: overlap = {{1.5, 2}, {3, 3.5}, {5, 6}};

I tried using Interval, IntervalUnion and IntervalIntersection, but nothing worked. The only working method that I found uses Piecewise functions where each interval is set as 1. By multiplying the two piecewise functions, I have something similar to the intersection, but the solution is very inefficient.

I hope I am clear and precise enough.

• Do you want the intersections of each of the intervals in the first list with each of the intervals in the second list? (Presumably you do not want intersections of corresponding entries in each of the two lists, since in the example your lists have different lengths.) Jul 28, 2014 at 14:01
• M can represent and operate on interval sets: List @@ IntervalIntersection[Interval @@ intervalsA, Interval @@ intervalsB] --> {{1.5, 2}, {3, 3.5}, {5, 6}} Jul 28, 2014 at 14:12
• Thanks a lot ! It works really well with the required speed ! :) I feel kind of stupid because I didn't use those intervals properly. Jul 28, 2014 at 14:17
• @alancalvitti Excellent - Why don't you put this as an answer?
– eldo
Jul 28, 2014 at 14:19
• Related: my own (old) question from Stack Overflow: (5784046) Jul 28, 2014 at 14:29

intervalsA = {{1, 2}, {3, 4}, {5, 7}, {8, 8.5}};
intervalsB = {{1.5, 3.5}, {4.1, 6}, {9, 10}};
IntervalIntersection @@ Interval @@@ {intervalsA, intervalsB}


Interval[{1.5, 2}, {3, 3.5}, {5, 6}]

• A bit classier, but slightly less efficient than List @@ IntervalIntersection[Interval @@ intervalsA, Interval @@ intervalsB]. Jul 28, 2014 at 14:35
• @Mammouth I don't see any difference in performance, and I think there shouldn't be as they are essentially equivalent. By the way the parentheses are extraneous here. Jul 28, 2014 at 15:17

or more general:

youFunction[intervals__] := Composition[
DeleteCases[#, Interval[]] &,
DeleteDuplicates,
(IntervalIntersection @@ # &) /@ # &,
Subsets[#, {2}] &,
Join[##] &
][intervals];

intervalsA = Interval /@ {{1, 2}, {3, 4}, {5, 7}, {8, 8.5}};
intervalsB = Interval /@ {{1.5, 3.5}, {4.1, 6}, {9, 10}};
youFunction[intervalsA, intervalsB]
(*{Interval[{1.5, 2}], Interval[{3, 3.5}], Interval[{5, 6}]}*)