Ответ на чернослив имеет правильную идею, но я чувствую, что нет смысла объяснять, как проверить перекрытие интервалов.Фактически, эта часть алгоритма выполняется за квадратичное время O(n^2), поскольку в какой-то момент она формирует все пары n^2, что не является необходимым.Что бы я сделал -
Очередь
Сначала создайте max-heap из вашего списка сегментов с координатой y в качестве ключа.Вы можете извлечь и удалить максимум за O(logn) время, так что это похоже на ту же сложность времени, что и сортировка, только со встроенным сованием.
heap = max_heap(segement_list)
output = []
while heap is not empty
segment = heap.pop() # max / highest
# trim / split segment
# append trimmed segment(s)
Пересечения
Теперь мы простонужно обрезать сегмент.Вместо того, чтобы соединять его с каждым другим сегментом и обрезать их по мере необходимости, мы будем использовать другую структуру данных, чтобы позволить нам быстро запрашивать потенциальные пересечения.Мы будем хранить каждый добавленный сегмент в бинарном дереве поиска с нижней координатой X в качестве ключа.Затем мы можем пройти по этому дереву, ища самый большой сегмент (по более низкой x-координате), меньший или равный сегменту, который мы собираемся добавить.
Ради того, чтобы следующие абзацы были менее раздутыми с техническими подробностямиПозволяет просто получить подробности реализации двух ключевых сравнений.Предположим, что сегмент a имеет меньшее значение lower_x, чем b (потому что в следующем параграфе мы всегда будем знать, что меньше).
# boolean- do `a` and `b` intersect
function intersects(a, b)
return a.upper_x >= b.lower_x
# boolean- is `b` a subsegment of `a`
function is_subsegment(a, b)
return a.upper_x >= b.upper_x
Нам также понадобятся три преобразования,используя те же a и b definition-
function merge(a, b)
a.upper_x = b.upper_x
function trim_left(a, b)
a.upper_x = b.lower_x
function trim_right(a, b)
b.lower_x = a.upper_x
Возвращаясь к идее запроса BST-дубля left_segment, полученного при запросе для нашего сегмента segment, и посмотрите, пересекаются ли они.Если они пересекаются, проверьте, если segment is_subsegment из left_segment.Если это так, прервите и continue перейдите к следующему сегменту в куче.В противном случае, если они пересекаются, нам нужно будет trim_right segment.Независимо от пересечения или нет, мы будем обрабатывать любые правосторонние пересечения.После этого мы можем merge модифицированные segment (на самом деле subsegment, как вы увидите) с left_segment, если они перекрываются.
left_segment - единственный сегмент, который может перекрываться слева, потому что мы объединяем все перекрывающиеся сегменты, когда они вставляются в BST.Однако, это не относится к правой стороне, так как наш segment еще должен быть обрезан справа.Нам нужно обрабатывать обрезку постепенно.
Примите right_segment как следующий сегмент после left_segment в дереве (обход в порядке).Сделайте копию segment под названием subsegment.Если subsegment пересекает right_segment, обрежьте его, вставьте subsegment в выходной массив, объедините два сегмента и удалите right_segment из BST.В противном случае просто вставьте subsegment в массив.Теперь мы можем объединить subsegment с left_segment, если они перекрываются.Если они этого не сделали, вставьте subsegment в BST и присвойте ему переменную left_segment.
Теперь мы повторяем этот процесс, пока не выйдем из segment, являющегося is_subsegment из left_segment.После этого мы повторяем весь процесс со следующим сегментом из кучи.
Анализ
Мы знаем, что формируем нашу максимальную кучу и выталкиваем максимум n разприведет к O(nlogn) сложности времени.Сложная задача - выяснить сложность времени для обработки пересечений.Заметьте, что для каждого сегмента, который мы обрабатываем, после того, как все subsegment обработаны и объединены, мы увеличим размер нашего BST не более чем на единицу.Это потому, что все наши subsegment объединяются вместе на каждой итерации, поэтому они в конечном итоге образуют один большой сегмент.Это означает, что наш BST не больше n, поэтому запрос и удаление / вставка в BST занимает O(logn) время.
Также обратите внимание, что для каждого сегмента, вставленного в BST, он будет пересекать только один сегмент только один раз, потому что, когда это произойдет, два (или более) будут объединены в один новый сегмент. Исключением является случай, когда сегмент является подсегментом left_segment, но в этом случае мы прекращаем работу, не создавая новых сегментов в любом случае, поэтому его +0 чистое изменение размера в любом случае. Используя эти знания в сочетании с предварительным наблюдением, что каждый сегмент в конечном итоге вносит не более одного нового сегмента в BST, мы можем заключить, что будет не более O(n) пересечений и, следовательно, вставок / удалений. Так что O(nlogn) время, чтобы поддерживать наш BST.
Учитывая, что остальные операции выполняются с постоянным временем, наша общая сложность по времени составляет O(nlogn) вместо O(n^2) при грубом форсировании для пересечений и обрезки.