具有挑战性的 Python 列表交集

Question

我有两个列表如下：

list_1 = [ [4,9], [10,14], [18,20], [21,23]]
list_2 = [ [3,5], [6,9], [10,11], [12,13], [14,16], [17,23] ]

我需要使用这些规则找到这两者的交集：

列表中的所有数字都已排序。
任何列表中都没有 0 或负数。
只有select那些范围差>=2的路口

所以使用上面的规则，交集结果应该是：

[ [6,9], [18,20],[21,23] ]

我在这张图片中通过在一条线上分配数字来表示这个问题：

更新：在下面发布了我自己的答案

Answer 1

按照你的定义，我得到的广义交集是：

list_1 = [ [4,9], [10,14], [18,20], [21,23]]
list_2 = [ [3,5], [6,9], [10,11], [12,13], [14,16], [17,23] ]
list_range1 = [item for sublist in [range(a, b+1) for a,b in list_1] for item in sublist]
list_range2 = [item for sublist in [range(a, b+1) for a,b in list_2] for item in sublist]
c = list(set(list_range1) & set(list_range2))
c.sort()
ans1 = [a for a in list_1 if (a[0] in c and a[1] in c)] + [a for a in list_2 if (a[0] in c and a[1] in c)]
ans2 = [a for a in ans1 if not a[0] == a[1]-1 ]

如果正确（不确定因为不确定我是否回答了这个问题），您的示例的答案也应该包含

[[4, 9], [10, 14]]

在list2 [3,5]中，[6,9]与[3,9]没有区别。如果你想区分它们，你应该为每个列表的第二项做-1，然后添加一个+1。

Answer 2

好的，我使用启发式方法得到了解决方案，但我确信它并不漂亮:(

def intersect_windows(list_1, list_2):
  if not list_1 or not list_2:
    return []

  list_1 = [range(x[0], x[1]) for x in list_1]
  list_2 = [range(x[0], x[1]) for x in list_2]

  result = []

  for s1 in list_1:
    for s2 in list_2:
      intr = [max(s1[0], s2[0]), min(s1[-1], s2[-1])+1]
      if (intr[1] - intr[0]) >= 2:
        result.append(intr)

  return result

##Usage

list_1 = [ [4,9], [10,14], [18,20], [21,23]]
list_2 = [ [3,5], [6,9], [10,11], [12,13], [14,16], [17,23] ]
intersect_windows(list_1, list_2)

[[6, 9], [18, 20], [21, 23]]

具有挑战性的 Python 列表交集

Challenging Python list intersection

python

list

math

set

intersection