Максимально возможное количество пересечений для любого из N заданных сегментов
Дан массив arr[] , состоящий из N пар типа {L, R} , каждая из которых представляет сегмент на оси X , задача состоит в том, чтобы найти максимальное количество пересечений сегмента с другими сегментами.
Примеры:
Input: arr[] = {{1, 6}, {5, 5}, {2, 3}}
Output: 2
Explanation:
Below are the count of each segment that overlaps with the other segments:
- The first segment [1, 6] intersects with 2 segments [5, 5] and [2, 3].
- The second segment [5, 5] intersects with 1 segment [1, 6].
- The third segment [2, 3] intersects with 1 segment [1, 6].
Therefore, the maximum number of intersections among all the segment is 2.
Input: arr[][] = {{4, 8}, {3, 6}, {7, 11}, {9, 10}}
Output: 2
Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы перебирать все сегменты и для каждого сегмента подсчитывать количество пересечений, проверяя его со всеми другими сегментами, а затем выводить максимум среди всех полученных пересечений.
Временная сложность: O(N 2 )
Вспомогательное пространство: O(1)
Эффективный подход. Описанный выше подход также можно оптимизировать на основе следующих наблюдений:
- Вышеупомянутый подход можно оптимизировать, пройдя каждый сегмент и вычислив количество сегментов, которые не пересекаются с текущим сегментом, используя двоичный поиск, и на основании этого найти количество сегментов, которые пересекаются с текущим сегментом.
- Предположим, что [L, R] — текущий отрезок, а [P, Q] — другой отрезок, тогда отрезок [L, R] не пересекается с отрезком [P, Q], если Q < L или P > R .
- Предположим, что X — это количество отрезков, не пересекающихся с отрезком [L, R] , тогда количество отрезков, пересекающих отрезок [L, R] = (N — 1 — X) .
Выполните следующие шаги, чтобы решить проблему:
- Сохраните все левые точки сегментов в массиве, скажем, L[] и все правые точки сегментов в массиве, скажем R[] .
- Отсортируйте оба массива L[] и R[] в порядке возрастания.
- Инициализируйте переменную, скажем, count как 0 , чтобы сохранить количество максимальных пересечений, которые имеет сегмент.
- Перейдите массив arr[] и выполните следующие шаги:
- Подсчитайте количество сегментов, оставшихся до текущего сегмента {arr[i][0], arr[i][1]} , используяlower_bound(), и сохраните его в переменной, скажем, cnt .
- Вычислить количество сегментов прямо до текущего сегмента {arr[i][0], arr[i][1]} с помощьюupper_bound() и увеличить на него значение cnt .
- Обновите значение count как максимальное значение count и (N – cnt – 1) .
- После выполнения вышеуказанных шагов выведите значение счетчика в качестве результата.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (N * log N)
Вспомогательное пространство: O(1)