Есть несколько сферических воздушных шаров, разбросанных в двумерном пространстве. Для каждого воздушного шара вводятся начальные и конечные координаты горизонтального диаметра. Поскольку он горизонтальный, координаты y не имеют значения, и, следовательно, достаточно координат x начала и конца диаметра. Начало всегда меньше конца.
Стрелку можно направить точно вертикально вверх из разных точек вдоль оси x. Воздушный шар с xstart и xend лопается от выстрела стрелы в x, если xstart ≤ x ≤ xend. Количество стрел, которые можно выпустить, не ограничено. Стрела, однажды выпущенная, продолжает двигаться вверх бесконечно.
Дан массив точек, где точки[i] = [xstart, xend] , верните минимальное количество стрел, которые необходимо выстрелить, чтобы лопнули все воздушные шары.
Ввод: баллы = [[10,16],[2,8],[1,6],[7,12]] Вывод: 2 Объяснение: Один из способов – выстрелить одной стрелой, например, в (разрыв воздушных шаров [2,8] и [1,6]), а другой стрелой в (разрыв двух других воздушных шаров). Пример 2:
Ввод: баллы = [[1,2],[3,4],[5,6],[7,8]] Результат: 4 Пример 3:
Ввод: баллы = [[1,2],[2,3],[3,4],[4,5]] Результат: 2 Пример 4:
Ввод: баллы = [[1,2]] Вывод: 1 Пример 5:
Ввод: баллы = [[2,3],[2,3]] Выход: 1
идея
Мы знаем концепцию слияния двух интервалов. Для объединения двух интервалов нам нужно сначала отсортировать интервалы по первому числу из числа. например: [[x, y]], если у нас есть такой интервал, нам нужно выполнить сортировку на основе x. Итак, в этой задаче нам также нужно начать с той же концепции, но с небольшим изменением, здесь нам нужно отсортировать на основе второго числа, т.е. сказать y.
Итак, давайте сделаем общее замечание здесь: Для интервала слияния – сортировка по первому номеру Для неперекрывающегося интервала – сортировка по второму номеру
Теперь мы отсортировали, и нам нужно найти те значения, которые больше определенного конца. Здесь проблема заключается в том, что стрелка проходит на бесконечном расстоянии от начала до конца. Поэтому нам нужно найти те точки, где начало > конец, если мы их найдем, то сможем обновить конец до 2-го элемента этого конкретного элемента и увеличить количество. Наконец, возвращая подсчет, учитывая минимальное количество стрелок, чтобы лопнуть воздушные шары.
Временная сложность: Здесь мы выполняем сортировку и один проход, поэтому сложность будет O(nlogn)
- Сортируйте интервалы на основе вторых значений заданных интервалов.
- Инициализируйте подсчет и возможный конец. Здесь возможно И может быть типа long, инициализированного минимальным значением.
- для
int [] p: очки– > > Проверьте, является ли начало, то есть p[0] > возможным концом. Если верно, то -> Обновите конец с помощью p[1] и увеличьте количество - Наконец, верните это количество, чтобы получить необходимое количество стрелок.
//my initial idea is to use the concept of merging the intervals started by sorting the points based on the first number.
//then just merge the intervals and count how many are different.
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0)
return 0;
// sort the elements based on the second element
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
// lets have a varible for storing the result
int arrowCount = 0;
long possibleEnd = Long.MIN_VALUE;
for (int [] p: points) {
if (p[0] > possibleEnd) {
possibleEnd = p[1];
arrowCount += 1;
}
}
return arrowCount;
}
}
Ссылка на Github: Ссылка
Небольшая Заметка
Этот метод также может быть применен для определения количества интервалов, чтобы удалить определенные интервалы, чтобы они не перекрывались. Следуйте тому же алгоритму, который обсуждался, с небольшим изменением в p[0] , а также в инструкции return. заданная длина Интервала - количество
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0)
return 0;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int count = 0;
int end = Integer.MIN_VALUE;
for (int [] interval: intervals) {
if (interval[0] >= end) {
end = interval[1];
count += 1;
}
}
return intervals.length - count;
}
}
Оригинал: “https://dev.to/rohithv07/452-minimum-number-of-arrows-to-burst-balloons-medium-17ec”