重叠的部分

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

有一个为此目的而设计的数据结构(有效识别区间重叠),它被称为区间树.