Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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[^]
Posted
Updated 19-Nov-21 12:38pm
Comments
[no name] 22-Nov-21 14:48pm    
Each "interval" (in the list) has an index / id. If the two "end points" you're comparing don't fall in the same interval (index / id), then it's "spanning". And you can easily deal with any that have any one end point outside of the range of the entire list if you track the min and max of the list.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900