Minimum Number of Arrows to Burst Balloons

Средняя№452сортировка по концу

Над прямой висят шарики, каждый занимает интервал [начало, конец]. Стрела, выпущенная вверх из точки x, лопает все шарики, где начало ≤ x ≤ конец, даже если только задевает край. Нужно найти наименьшее число стрел, которые лопнут все шарики. Наш пример: [4, 8], [10, 12], [1, 6], [7, 9], [2, 4], [9, 11] — ответ 3.

452 Minimum Number of Arrows to Burst BalloonsРазбор · 1×

Пример: [4, 8], [10, 12], [1, 6], [7, 9], [2, 4], [9, 11]. Шарики нарисованы по порядку концов, каждая стрела — вертикальная линия в точке, откуда её выпустили.

[2, 4][1, 6][4, 8][7, 9][9, 11][10, 12]0123456789101112
ещё впередитекущий шарик, новая стрелалопнул

Сортируем по концу: 4, 6, 8, 9, 11, 12

01/18
сначала · назад · пуск · шаг
Скорость
1function findMinArrowShots(points):
2 sort points by end
3 arrows = 1
4 arrowAt = points[0].end
5 for each [start, end] after the first:
6 if start > arrowAt:
7 arrows = arrows + 1
8 arrowAt = end
9 return arrows
состояние
arrows
–
arrowAt
–
start
–
end
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Шарик, который кончается раньше всех, должна лопнуть какая-то стрела не правее его конца. Выстрел ровно в его конец ничего не теряет: любой другой шарик, который могла лопнуть такая стрела, начинается раньше этого конца, а кончается позже — значит, тоже его накрывает.
  2. Поэтому каждая новая стрела летит в конец первого шарика, мимо которого прошла прошлая. Шарик пропущен, только если начинается правее arrowAt; тот, что начинается ровно в arrowAt, задет и лопается.
  3. Каждая новая стрела — для шарика, который начинается правее прошлой стрелы, поэтому у шариков, получивших стрелы, [2, 4], [7, 9] и [10, 12], нет общих точек. Одна стрела не лопнет два из них, значит, меньше 3 стрел не бывает.

Сложность

Время O(n log n): сортировка; проход после неё — O(n). Память O(1), не считая того, что нужно сортировке.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.