Эффективные алгоритмы поиска для расчета сечения на множестве отрезков

Question

У меня большой набор данных сегментов строки.Каждый сегмент строки состоит из [x-start,x-end].Я ищу эффективные алгоритмы для расчета для заданной x позиции множества пересекающихся линий.

Answer 1

Ответ Ив-Дауста: Дерево интервалов - ваш лучший друг

Answer 2

1. Найти все строки, где x ∈ [start;конец] в O (n)
2. В найденном списке строк найдите строку с минимальным началом и строку с максимальным концом (в линейном времени).Таким образом, у вас будет две точки (A, B)

3. Найдите все линии, где:

   • A ∈ [start;конец]
   • B ∈ [начало;конец]
   • начало ∈ [A;B] и конец ∈ [A, B] и поместите их в Set.

Общая сложность времени должна быть O (n)