Hi, consider two lists each with a set of intervals (lists with two elements e1 < e2):
List1 = [[1790, 1850], [1850, 1910], [1910, 1970], [1970, 2030], [2090, 2150], [2150, 2210], [2210, 2270], [2270, 2330], [2330, 2390], [2390, 2450], [2450, 2510], [2510, 2570], [2570, 2630], [2630, 2690], [2690, 2750]]
List2 = [[1900, 1960], [1960, 2020], [2020, 2080], [2080, 2140], [2200, 2260], [2260, 2320], [2320, 2380], [2380, 2440], [2440, 2500], [2500, 2560], [2560, 2620], [2620, 2680], [2680, 2740]]
the cartesian product of these two lists is a list with all the possible combinations (size = len(List1) * len(List2) = 15 * 13 = 195)
However what I want to compute are the combinations where there is no overlapping of intervals e.g.
[1790, 1850]
does not overlap with any element of List2; This results in 13 combinations.
[1850, 1910]
overlaps with
[1900, 1960]
this results in an added 12 combinations
[1910, 1970]
overlaps with
[1900, 1960] and [1960, 2020]
this results in an added 11 combinations
and so on and so forth. I would like to extend this computation for more than these 2 lists and eliminate any combination that has overlapping intervals e.g. 8 lists, with a total of 9*9*15*13*12*7*5*2 = 13,267,800
[[[1081, 1156], [1141, 1216], [1201, 1276], [1741, 1816], [1801, 1876], [1861, 1936], [1921, 1996], [1981, 2056], [2041, 2116]], [[1170, 1250], [1230, 1310], [1770, 1850], [1830, 1910], [1890, 1970], [1950, 2030], [2010, 2090], [2070, 2150], [2130, 2210]], [[1790, 1850], [1850, 1910], [1910, 1970], [1970, 2030], [2090, 2150], [2150, 2210], [2210, 2270], [2270, 2330], [2330, 2390], [2390, 2450], [2450, 2510], [2510, 2570], [2570, 2630], [2630, 2690], [2690, 2750]], [[1900, 1960], [1960, 2020], [2020, 2080], [2080, 2140], [2200, 2260], [2260, 2320], [2320, 2380], [2380, 2440], [2440, 2500], [2500, 2560], [2560, 2620], [2620, 2680], [2680, 2740]], [[2015, 2090], [2075, 2150], [2135, 2210], [2195, 2270], [2255, 2330], [2315, 2390], [2375, 2450], [2435, 2510], [2495, 2570], [2555, 2630], [2615, 2690], [2675, 2750]], [[2310, 2390], [2370, 2450], [2430, 2510], [2490, 2570], [2550, 2630], [2610, 2690], [2670, 2750]], [[2435, 2505], [2495, 2565], [2555, 2625], [2615, 2685], [2675, 2745]], [[2560, 2640], [2620, 2700]]]
What I have tried:
So far found nothing similar. The best I could find was in
algorithm - search for interval overlap in list of intervals? - Stack Overflow[
^]