合并列表中的重叠项

Question

我的目标是合并下面这个例子列表中重叠的元组。

如果一个元组的范围在下一个元组的范围内，那么这两个元组就需要合并。合并后的元组应该覆盖这两个元组的范围，也就是从最小值到最大值。例如，[(1,6),(2,5)] 会变成 [(1,6)]，因为 [2,5] 在 [(1,6)] 的范围内。

mylist=[(1, 1), (1, 6), (2, 5), (4, 4), (9, 10)]

这是我尝试的结果：

c=[]
t2=[]
for i, x in enumerate(mylist):
    w=x,mylist[i-1]
    if x[0]-my[i-1][1]<=1:
        d=min([x[0] for x in w]),max([x[1] for x in w])
        c.append(d)
for i, x in enumerate(set(c)):
    t=x,c[i-1]
    if x[0]-c[i-1][1]<=1:
        t1=min([x[0] for x in t]),max([x[1] for x in t])
        t2.append(t1)
print sorted(set(t2))

得到的输出：

[(1, 6), (1, 10)]

期望的输出：

[(1, 6), (9, 10)]

有没有什么建议可以让我得到期望的输出（如果可以的话，尽量少写几行代码）？谢谢。

Answer 1

你可以用 O(nlogn) 的时间来解决这个问题。

首先，你需要把所有的区间按照它们的起始点进行排序。接下来，你创建一个新的栈，然后对每个区间执行以下操作：

如果栈是空的，就把当前的区间放进去；

如果栈不是空的，你需要检查栈里第一个区间是否和当前的区间有重叠。如果有重叠，就把栈里的那个区间弹出，和当前的区间合并，然后把合并后的结果再放回栈里。如果没有重叠，就直接把当前的区间放进栈里。等你检查完所有的区间后，栈里就会包含所有合并后的区间。

Answer 2

根据@Valera的回答，这里是用Python实现的代码：

mylist=[(1, 6), (2, 5), (1, 1), (3, 7), (4, 4), (9, 10)]

result = []
for item in sorted(mylist):
    result = result or [item]
    if item[0] > result[-1][1]:
        result.append(item)
    else:
        old = result[-1]
        result[-1] = (old[0], max(old[1], item[1]))

print result # [(1, 7), (9, 10)]