перекрывающиеся сегменты

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

Для этой конкретной цели разработана структура данных (эффективная идентификация интервальных перекрытий), она называется дерево интервалов .

Answer 2

Сначала отсортируйте список (для сравнения сначала используйте начальную точку, затем конечную точку). Затем просмотрите список и удалите все кортежи, которые перекрывают предыдущий элемент в списке. Это O (nlog (n)) для сортировки и O (n), чтобы пройти по списку.

Надеюсь, это поможет.