有点难以解释，所以我在下面举了一个例子。
所以我有列表 A，看起来像这样 - (20-40,60-80,100-200)但它们可以是任何范围。
列表 B (15-35,60-85,50-150)，正如你所看到的，B 中的三个范围确实与 A 中的范围交叉，但我需要轻松确定它们是否交叉(有些没有(以及它们"错位"的程度或它们的差异程度。例如，对于两个列表中的第一个元素，B 重叠，但在范围的开始和停止处太低 5。
到目前为止，我唯一的想法是创建一个非常慢的"for 循环"系统来检查范围，但对于我拥有的大量值来说，这非常慢。
我认为这将是一个微不足道的问题，但到目前为止我还没有找到任何简单的东西。任何帮助，不胜感激。 谢谢。
我将假设范围列表已排序并且它们内部不会重叠。如果这不是真的，这个答案将需要一些修改。
首先，让我们编写一个帮助程序函数，省去检查两个范围是否重叠的麻烦。
def compare(r1, r2):
low_1, high_1, low_2, high_2 = parse(r1, r2) # parse is left as an exercise because I'm lazy
if (high_1 < low_2):
return -1
elif (high_2 < low_1):
return 1
return 0 # They overlap!
现在我们有了帮助程序函数，我们可以从一开始就基于我们的假设实现一个搜索算法。
def seek(list_of_ranges_1, list_of_ranges_2):
len_1 = len(list_of_ranges_1)
len_2 = len(list_of_ranges_2)
head_1, head_2 = 0
while(true):
# Given that the lists are sorted, if you reach the end of one, there are no more overlaps
if (head_1 == len_1 || head_2 == len_2):
break
r1 = list_of_ranges_1[head_1]
r2 = list_of_ranges_2[head_2]
test_value = compare(r1,r2)
if (test_value == -1):
head_1 +=1
elif (test_value == 1):
head_2 +=1
else:
# This is the complicated case. In the other cases, there was no overlap,
# so we could safely move the lower range forward. But now, we
# have ranges that overlap, and there could be several ranges in
# one list that overlap with a single range in the first list.
# The solution to this is to iterate the range that has the lower
# high_value. IE, if we has r1 = 10-15 and r2 = 12-25, we would
# iterate head_1, but if r2 was 12-13, we would iterate head_2, to account for
# the possibility that the next range is 14-n, and overlaps with the
# same range 10-15.
此代码假设解析函数和 else 情况已正确实现，将获得您想要的结果。此外，假设循环的每次迭代head_1和head_2严格增加，复杂度为 O(n + m(。