Меры перекрытия

Question

У меня есть список кортежей мер, из которого я хочу удалить перекрывающиеся элементы и обновить начало и конец, где перекрытие не является полным. НАПРИМЕР

  s------------------------------------e
       s1------------------------e1
Remove S1, E1.

  s----------------------e
           s1----------------------e1
Change S,E to S,E1 and remove S1,E1.

Я попытался сделать это, используя метод "грубой силы" - циклически проходя по списку и сравнивая начало и конец, но для списка из 70 элементов это навсегда 0(n2).

Я думал, что мог бы использовать SortedDictionary, но он не может справиться с записями, которые являются дубликатами (и некоторые записи могут быть дублированы).

Он также должен справляться с изменениями значений, поскольку список просматривается, поэтому я не уверен, что сортировка списка - лучший вариант.

Похоже, алгоритм Бентли-Оттомана может работать, но я не уверен, как его реализовать. Он пересекает список с вертикальной линией, находя значения, которые больше, чем текущее начало (или меньше, чем в случае перекрытия). Кажется, это не будет намного лучше, чем метод грубой силы.

Может кто-нибудь предложить какой-нибудь код, который я мог бы использовать для этого?