Найдите минимальное количество стрел, необходимое для того, чтобы взорвать все шарики

Дан массив points[][] размера N , где points[i] представляет воздушный шар над областью координат X от points[i][0] до points[i][1] . Координаты Y значения не имеют. Все шары необходимо лопнуть. Чтобы взорвать воздушный шар, можно запустить стрелу в точке (x, 0) , которая летит вертикально вверх и лопает все воздушные шары, удовлетворяющие условию points[i][0] <= x <= points[i][1] . Задача состоит в том, чтобы найти минимальное количество стрел, необходимое для того, чтобы лопнуть все шарики.

Примеры:

Input: N = 4, points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}}
Output: 2
Explanation: One way is to shoot one arrow for example at x = 6 (bursting the balloons [2, 8] and [1, 6]) and another arrow at x = 11 (bursting the other two balloons).

Input: N = 1, points = {{1, 6}}
Output: 1
Explanation: One single arrow can burst the balloon.

Подход: Данную проблему можно решить, используя Жадный подход, чтобы найти воздушные шары, которые перекрывают друг друга, чтобы стрела могла пройти через все такие воздушные шары и лопнуть их. Чтобы сделать это оптимально, отсортируйте массив по координате X в порядке возрастания. Итак, теперь рассмотрим 2 воздушных шара, если второй воздушный шар начинается перед первым воздушным шаром, то он должен заканчиваться после первого воздушного шара или в том же месте.

For example [1, 6], [2, 8] -> the second balloon starting position i.e 2 which is before the ending position of the first balloon i.e 6, and since the array is sorted the end of the second balloon is always greater than the end of the first balloon. The second balloon end i.e 8 is after the end of the first balloon i.e 6. which shows us the overlapping is there between [2, 6].

Выполните следующие шаги, чтобы решить проблему:

• Отсортируйте массив в соответствии с конечным положением воздушных шаров, используя выражение компаратора/лямбда Arrays.sort(points, (a, b)-> Integer.compare(a[1], b[1])).
• Создайте переменную стрелку и инициализируйте ее значением 1 (поскольку для взрыва воздушных шаров потребуется как минимум одна стрелка).
• Сделайте конец переменной и инициализируйте ее точками[0][1] , которые будут хранить конец первого шара.
• Переберите диапазон [1, N), используя переменную i , и выполните следующие шаги:
  • Проверьте, меньше ли начало следующего шара points[i][0] чем конечная переменная end .
  • Если да, то продолжайте итерацию.
  • В противном случае увеличьте количество стрелок на 1 и установите значение конца как points[i][1] .
• После выполнения вышеуказанных шагов выведите значение стрелки в качестве результирующего необходимого количества стрелок.

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

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