Учитывая набор интервалов, найдите интервал, который имеет максимальное количество пересечений (а не длину конкретного пересечения). Поэтому, если нужно вернуть вход (1,6) (2,3) (4,11), (1,6). Некоторые предлагают использовать Дерево Интервала, чтобы сделать это в O (nlogn), но я не понял, как построить и использовать Дерево Интервала после прочтения его вики-страницы. Я считаю, что это можно сделать, выполнив какой-то алгоритм сортировки и сканирования. Если дерево Интервал является единственным вариантом, пожалуйста, просветите меня, как его построить/использовать. Спасибо.
Учитывая набор интервалов, найдите интервал, который имеет максимальное количество пересечений
Ответ 1
Примечание. Алгоритм David Eisenstat имеет лучшую производительность, чем эта.
Простой алгоритм плоской развертки сделает это в O(nlogn + m*n), где m - максимальное количество пересечений с любым одним интервалом.
Сортировка интервальных конечных точек. Следите за активными сегментами. Достигнув начальной точки, увеличьте количество пересечений всех активных интервалов и установите новый интервал пересечения в число активных интервалов (исключая себя). При достижении конечной точки удалите интервал из активных интервалов.
Ответ 2
Не используйте дерево интервалов. Создайте событие для каждой конечной точки интервала, чтобы каждый интервал имел событие начала и событие остановки. Обработать эти события по порядку. (Заказ начинается до остановки, если пересечение мера-нуль считается пересечением или останавливается до начала иначе).
Инициализировать карту C от интервалов до цифр. Инициализируйте начальное число s = 0 и счетчик остановки t = 0. Чтобы обработать событие начала для интервала i, установите s = s + 1, а затем C (i) = - (t + 1). Для обработки события остановки для интервала я задайте t = t + 1, а затем C (i) = C (i) + s.
В конце, C отображает интервалы на их подсчеты пересечения. Этот алгоритм является O (n log n) из-за сортировки; что время работы оптимально, если конечные точки можно добавлять и сравнивать только с помощью довольно стандартных методов вычислительной геометрии.