Алгоритм для нахождения количества пересечений отрезков в последовательности(списке)?

Question

[artur_agishev]

Можете написать минимальный по сложности(время) алгоритм для нахождения количества пересечений отрезков в последовательности(списке)

Пример
Отрезки
0 3
1 1
2 4
Последовательность
1 2 3 4 5
Вывод
1 2 2 2 1
То есть пересечение происходит по всей длине отрезка

Comments

[kaktak255]

какое применение этому алгоритму?

[artur_agishev]

kaktak255, часть кода для сдачи задачи

Answer 1

[Wataru]

Заведите массив из нулей. Для каждого отрезка сделайте +1 в координату его левого конца и -1 в координату, следующую за правым концом.

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

Это если вам надо весь массив, как в примере, выводить. Не знаю специфику вашей задачи, может эффективнее будет класть в массив пары {координата, +-1} и сортировать. Потом точно также обойти слева направо поддерживая счетчик.

Comments

[Сергей Соколов]

с такими +1 и -1 точечный отрезок [1, 1] в пролёте

[Wataru]

Сергей Соколов, Почему? +1 ставится в позицию 1, -1 в позицию 2 (я же написал "в координату за правым концом").
При проходе сделаем +1 в позиции 1 и выведем 1. Потом в позиции 2 вычтем 1 и получим правильный 0.

Edit, слегка подправил формулировку в ответе, чтобы понятнее было.

[dollar]

Жаль для отрезков на плоскости такое не прокатит. Было бы интересно увидеть оптимизацию.

[Wataru]

dollar, Обобщение это задачи (подсчитать сколько клеток покрыто отрезками на прямой) - это прямоугольники на плоскости. И там точно такой же трюк есть: в 4 угла поставить +1 и -1 (по диаганали знаки, правые/верхние сдвинуты на 1 наружу). Потом делаем 2 прохода по плоскости - сначала по строкам, потом по столбцам: и также накапливаем частичные суммы.

Если плоскость большая и надо, допустим, самую плотно покрытую точку найти - то можно двумерное дерево отрезков запилить. Или для экономии памяти - мою любимую структуру данных: дерево отрезков декартовых деревьев (в бинарном дереве точно также можно делать добавление на отрезке, как и в дереве отрезков).

Если же брать другое обобщение этой задачи - именно отрезки на плоскости, то там уже общих пересечений особо может и не быть вообще. Ибо два отрезка на плоскости пересекаются по точке. Что вы там хотите найти - все точки пересечения?

Но в таких задачах все-равно часто работает метод сканирующей прямой (решение, что я привел к вопросу - по сути и есть частный случай этого метода). Там можно, например, найти есть ли пересечение среди N отрезков за N log N.

Answer 2

[Griboks]

Если я правильно понимаю типы данных, то перебор списка с обычной проверкой counter+= left<=x<=right будет наиболее быстрым с учетом скорости выделения и освобождения памяти.

Comments

[Wataru]

Это если вам надо подсчитать только количество отрезков в одной конкретной точке. В вопросе в примере выводятся количества для всех клеток сразу. В этом случае ваш метод далеко не самый оптимальный. И еще, в каком языке есть такие двойные сравнения? Придется писать left<=x && x<=right