Python 中两个范围列表的交集

我的一个朋友向我传递了他最近收到的一个面试问题，我对我的解决方案不太满意。问题如下：

• 你有两个清单。
• 每个列表将包含长度为 2 的列表，表示一个范围（即 [3,5] 表示从 3 到 5（含）的范围）。
• 您需要返回集合之间所有范围的交集。如果我给你 [1,5] 和 [0,2]，结果将是 [1,2]。
• 在每个列表中，范围将始终增加并且从不重叠（即，它将是 [[0, 2], [5, 10] ... ] 而不是 [[0,2], [2,5] ... ] ）

一般来说，列表的排序或重叠方面不存在“陷阱”。

Example:

a = [[0, 2], [5, 10], [13, 23], [24, 25]]
b = [[1, 5], [8, 12], [15, 18], [20, 24]]

预期输出：[[1, 2], [5, 5], [8, 10], [15, 18], [20, 24]]

我的懒惰解决方案涉及将范围列表扩展为整数列表，然后进行集合交集，如下所示：

def get_intersection(x, y):
    x_spread = [item for sublist in [list(range(l[0],l[1]+1)) for l in x] for item in sublist]
    y_spread = [item for sublist in [list(range(l[0],l[1]+1)) for l in y] for item in sublist]
    flat_intersect_list = list(set(x_spread).intersection(y_spread))
...

但我想有一个既可读又更高效的解决方案。

如果您不介意的话，请解释一下您将如何在精神上解决这个问题。时间/空间复杂性分析也会有所帮助。

Thanks

[[max(first[0], second[0]), min(first[1], second[1])] 
  for first in a for second in b 
  if max(first[0], second[0]) <= min(first[1], second[1])]

给出答案的列表理解：[[1, 2], [5, 5], [8, 10], [15, 18], [20, 23], [24, 24]]

分解一下：

[[max(first[0], second[0]), min(first[1], second[1])] 

第一项的最大值，第二项的最小值

for first in a for second in b 

对于第一项和第二项的所有组合：

if max(first[0], second[0]) <= min(first[1], second[1])]

仅当第一个的最大值不超过第二个的最小值时。

如果您需要压缩输出，那么以下函数可以做到这一点（在O(n^2)时间，因为从列表中删除是O(n)，我们执行的一个步骤O(n) times):

def reverse_compact(lst):
    for index in range(len(lst) - 2,-1,-1):
        if lst[index][1] + 1 >= lst[index + 1][0]:
            lst[index][1] = lst[index + 1][1]
            del lst[index + 1]  # remove compacted entry O(n)*
    return lst

它连接接触的范围，因为它们是in-order。它以相反的方式进行，因为这样我们就可以执行此操作in place并删除压缩的条目。如果我们不反过来做，删除其他条目就会破坏我们的索引。

>>> reverse_compact(comp)
[[1, 2], [5, 5], [8, 10], [15, 18], [20, 24]]

• 压缩函数可以进一步简化为O(n)通过进行前向就地压缩并复制回元素，因为每个内部步骤都是O(1)（get/set 而不是 del），但这可读性较差：

这运行在O(n)时间和空间复杂度：

def compact(lst):
    next_index = 0  # Keeps track of the last used index in our result
    for index in range(len(lst) - 1):
        if lst[next_index][1] + 1 >= lst[index + 1][0]:
            lst[next_index][1] = lst[index + 1][1]
        else:    
            next_index += 1
            lst[next_index] = lst[index + 1]
    return lst[:next_index + 1]

使用任一压缩器，列表理解是这里的主导术语，时间 =O(n*m), 空间 =O(m+n)，因为它比较两个列表的所有可能组合，没有早期出局。这确实not利用提示中给出的列表的有序结构：您可以利用该结构将时间复杂度降低到O(n + m)因为它们总是增加并且从不重叠，这意味着您可以一次完成所有比较。

请注意，解决方案不止一种，希望您能够解决问题，然后迭代改进它。

满足所有可能输入的 100% 正确答案并不是面试问题的目标。就是看一个人如何思考和应对挑战，以及是否能够推理出解决方案。

事实上，如果你给我一个 100% 正确的教科书答案，那可能是因为你以前见过这个问题并且你已经知道解决方案......因此这个问题对我作为面试官没有帮助。“检查一下，可以反省在 StackOverflow 上找到的解决方案。”这个想法是看着你解决问题，而不是重复解决方案。

太多的候选人只见树木，不见森林：承认缺点并提出解决方案是回答面试问题的正确方法。你不必有解决方案，你必须展示你将如何解决问题。

如果可以的话你的解决方案很好解释一下并详细说明使用它的潜在问题。

我通过未能回答面试问题获得了现在的工作：在花费了大部分时间尝试之后，我解释了为什么我的方法不起作用，以及如果有更多时间我会尝试第二种方法，以及我在其中看到的潜在陷阱方法（以及为什么我最初选择第一个策略）。