查找多个元组列表交集的高效/可伸缩Python算法？

Question

我有多个包含元组的列表，例如

list_A = [(start_1, end_1), (start_2, end_2), (start_3, end_3)]
list_B = [(start_4, end_4), ...]

是否有一种聪明的方法可以生成一个只包含交叉点的result_list，而不必以嵌套方式O（n^m）搜索每个列表

例如：

list_A = [('8:00 AM', '10:00 AM'), ('12:59 PM', '3:00 PM'), ('5:04 PM', '7:23 PM')]
list_B = [('9:06 AM', '9:47 AM'), ('9:51 AM', '12:45 PM'), ('1:33 PM', '2:52 PM'), ...]
list_C = [...]
list_D = [...]
# etc. etc. (m lists)

有关此问题的说明，请参见下图：

Answer 1

可以在O（m*n）中执行以下操作-

r = [[1,3], [5,7], [9,11]]
s = [[2,4], [5,6], [7,9], [11,14]]

r = [[i[0],i[1]+1] for i in r] #to make it inclusive at ends
s = [[i[0],i[1]+1] for i in s] #to make it inclusive at ends

overlapping_ranges = [set(range(*i[0])).intersection(set(range(*i[1]))) for i in list(itertools.product(r, s))]
overlapping_ranges = [i for i in overlapping_ranges if i] #removing nullsets

[{2, 3}, {5, 6}, {7}, {9}, {11}]