Проверить, могут ли N заданных прямых пересекаться K вертикальными прямыми.

Даны N горизонтальных линий, представленных массивом position[][] размера N, где position[i] представляет собой i ^-ю горизонтальную линию, которая имеет x -координаты от position[i][0] до position[i][1] и целое число K, которое представляет собой максимальное количество вертикальных линий, которые можно нарисовать, задача состоит в том, чтобы проверить, могут ли N заданных прямых пересекаться не более чем K вертикальными линиями.

Примеры:

Input: N = 4, K = 2, position[][] = [[1, 4], [6, 8], [7, 9], [10, 15]]
Output: NO
Explanation: In the given example, draw lines at [1, 7, 10]. The line drawn at 1 will intersect the first line, the line at position 7 will intersect both the second and third lines, and the line drawn at 10 will intersect the fourth line. Hence, a minimum of 3 rods is required. Hence, it is not possible

Input: N = 5, K = 3, position[][] = [[1, 6], [3, 5], [2, 4], [8, 12], [10, 24]]
Output : YES

Подход: Идея состоит в том, чтобы использовать жадный подход для решения этой проблемы, сортируя массив position[][] и с помощью 1 строки пересекая как можно больше строк и так далее. Выполните следующие шаги, чтобы решить проблему:

• Отсортируйте массив position[][] в порядке возрастания.
• Инициализируйте переменные ans как 1 для хранения ответа и r как position[0][1] для хранения конечной точки до определенной точки, другие горизонтальные линии могут быть для пересечения с данной рассматриваемой вертикальной линией.
• Переберите диапазон [1, N], используя переменную, скажем, I , и выполните следующие шаги:
  • Если position[i][0] меньше r, то установите значение r равным минимуму r или position[i][1].
  • В противном случае добавьте значение ans на 1 и установите значение r как position[i][1].
• Если к больше чем равно ans, то выведите «YES» и выведите «NO» в противном случае.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(NlogN)
Вспомогательное пространство: O(1)