重叠段落

Question

我有一个很大的列表，里面是两个元素的元组，这些元组代表了线段的起点和终点。列表的格式如下：

list = [ (1,4), (2, 3), (10, 20), (18, 45) ] 

这个列表里有4条线段，每条线段都有它的起点和终点。我想要去掉那些重叠的线段。最后我希望得到一个这样的列表：

list = [ (1,4), (10,20) ]. 

我已经写了一个函数，这个函数可以接收一对线段作为输入，如果它们的坐标重叠，就返回1：

def test_overlap(s1,e1,s2,e2):
    if (s1 <= e2 and e1 >= s2) or (e1 >= s2 and s1 <= e2):
        return 1
    if (s1 <= s2 and e1 >= e2) or (s1 >= s2 and e1 <= e2):
        return 1

但是我不知道怎么高效地比较这个大列表中的每一对线段。任何帮助都将非常感谢！

Answer 1

首先，把列表排序（比较的时候先用起始点，再用结束点）。然后遍历这个列表，去掉所有与前一个元素重叠的元组。排序的时间复杂度是O(nlog(n))，遍历列表的时间复杂度是O(n)。

希望这能帮到你。

Answer 2

有一种数据结构专门用来解决这个问题（高效识别区间重叠），它叫做区间树。