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

Опубликовано: 22 Сентября, 2022

Дан массив 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:

  1. The first segment [1, 6] intersects with 2 segments [5, 5] and [2, 3].
  2. The second segment [5, 5] intersects with 1 segment [1, 6].
  3. 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ