поиск перекрытия интервалов в списке интервалов?
Скажем, [a, b] представляет интервал на реальной прямой от a до b, a
Дан список интервалов ([x1, y1], [x2, y2], ...), каков наиболее эффективный способ найти все такие интервалы, которые перекрываются с [x, y]?
Очевидно, я могу попробовать каждый и получить его за O (n). Но мне было интересно, могу ли я каким-то умным способом отсортировать список интервалов, я мог бы найти / один / перекрывающийся элемент в O (журнал N) с помощью двоичного поиска, а затем `` осмотреться '' из этой позиции в списке, чтобы найти все перекрывающиеся интервалы. Однако как мне отсортировать интервалы, чтобы такая стратегия работала?
Обратите внимание, что могут быть перекрытия между элементами в самих элементах списка, что и усложняет задачу.
Я пробовал это, сортируя интервалы по их левому, правому и среднему концам, но, похоже, ни один из них не приводит к исчерпывающему поиску.
Помогите?