8. Minimum Number of Arrows
«Простота — необходимое условие надежности».
— Эдсгер Дейкстра
Задача Minimum Number of Arrows to Burst Balloons (LeetCode 452) — это элегантная геометрическая интерпретация классической задачи о покрытии интервалов точками (Stabbing Intervals Problem / Set Cover on Intervals).
Она логически завершает наш цикл интервальных алгоритмов вслед за 6. Interval Scheduling и 7. Non-overlapping Intervals. Если в задаче о планировании мы выбирали совместимые интервалы, а в Non-overlapping — удаляли конфликты, то здесь мы ищем минимальное число уколов (выстрелов), способных проткнуть все имеющиеся одномерные отрезки.
1. Постановка задачи и постановка на собеседовании
Условие:
Есть горизонтальные воздушные шары, расположенные на числовой прямой. Каждый шар задан отрезком points[i] = [x_start, x_end].
Стрела выпускается вертикально вверх из координаты x. Она лопает любой шар, отрезок которого включает точку выстрела, то есть $x_{start} \le x \le x_{end}$. Одной стрелой можно пробить бесконечно много шаров, если все они перекрывают координату $x$.
Требуется найти минимальное количество стрел, необходимое для уничтожения всех шаров.
Вход: points = [[10, 16], [2, 8], [1, 6], [7, 12]]
Выход: 2
Пояснение:
- Первая стрела в точке x = 6 пробивает шары [2, 8] и [1, 6].
- Вторая стрела в точке x = 12 (или 11) пробивает [10, 16] и [7, 12].
flowchart TD
classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
classDef error fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
classDef entry fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
subgraph Geometry["Геометрия выстрелов"]
B1["Шар 1: [1, 6]"]:::process
B2["Шар 2: [2, 8]"]:::process
B3["Шар 3: [7, 12]"]:::process
B4["Шар 4: [10, 16]"]:::process
end
A1["Стрела 1 в x = 6"]:::success -.-> B1
A1 -.-> B2
A2["Стрела 2 в x = 12"]:::warning -.-> B3
A2 -.-> B4
Вопросы интервьюеру (Senior Checklist):
- Может ли массив быть пустым? Да, при $N = 0$ требуется 0 стрел.
- Может ли шар быть точкой? Да, если $x_{start} == x_{end}$, выстрел в эту координату пробивает его.
- Считается ли касание границ пробитием? Да, если стрела пущена в точку $x = 6$, а шар начинается в $6$ или заканчивается в $6$, он лопается ($x_{start} \le x \le x_{end}$).
- Возможно ли переполнение
int? Координаты могут принимать значения от $-2^{31}$ до $2^{31}-1$. Если вычитать координаты при сортировке (a - b), произойдет целочисленное переполнение (integer overflow). В Go сравнение должно производиться через безопасный компараторcmp.Compareили операторы<,>.
2. Жадный выбор: Почему стрелять нужно строго в правый край?
Представим шар, который заканчивается раньше всех остальных на числовой прямой (назовем его координату конца $E$).
Чтобы лопнуть этот шар, стрела обязана приземлиться в диапазоне $[x_{start}, E]$.
Куда выгоднее всего направить выстрел?
Если мы выстрелим левее $E$, мы проткнем этот шар, но упустим шанс задеть другие шары, расположенные дальше вправо.
Стреляя точно в крайнюю правую допустимую точку $x = E$:
- Мы гарантированно пробиваем текущий шар.
- Мы максимизируем покрытие всех последующих шаров, которые начались до координаты $E$ включительно!
Это хрестоматийный пример жадного выбора (Greedy Choice Property): локально оптимальное решение (выстрел в правый конец первого непробитого шара) математически гарантирует глобальный минимум стрел.
3. Алгоритм и визуализация
flowchart TD
classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
classDef error fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
classDef entry fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
Start["Старт: points [][]int"]:::entry --> CheckEmpty{"len == 0?"}:::warning
CheckEmpty -- "Да" --> RetZero["Возврат 0"]:::error
CheckEmpty -- "Нет" --> Sort["Сортировка по x_end<br/>slices.SortFunc"]:::process
Sort --> Init["arrows = 1<br/>end = points[0][1]"]:::entry
Init --> Loop["Цикл по i = 1 .. N-1"]:::process
Loop --> CheckOverlap{"points[i][0] > end?<br/>(Шар правее стрелы)"}:::warning
CheckOverlap -- "Да (не пробит)" --> NewArrow["arrows++<br/>end = points[i][1] (Новая стрела)"]:::error
CheckOverlap -- "Нет (пробит)" --> Skip["Шар пробит текущей стрелой<br/>(end не меняем)"]:::success
NewArrow --> More{"Есть еще шары?"}:::process
Skip --> More
More -- "Да" --> Loop
More -- "Нет" --> Ret["Возврат arrows"]:::entry
4. Реализация на Go 1.22+
package intervals
import (
"cmp"
"slices"
)
// FindMinArrowShots находит минимальное число стрел для пробития всех шаров.
// Временная сложность: O(N log N) из-за сортировки.
// Пространственная сложность: O(1) дополнительной памяти (in-place).
func FindMinArrowShots(points [][]int) int {
if len(points) == 0 {
return 0
}
// Сортируем шары по возрастанию правого края (x_end).
// В Go 1.21+ slices.SortFunc инлайнится компилятором,
// а cmp.Compare защищает от переполнения при разности больших int32/int64.
slices.SortFunc(points, func(a, b []int) int {
return cmp.Compare(a[1], b[1])
})
// Первая стрела целится в правый край первого шара
arrows := 1
end := points[0][1]
for i := 1; i < len(points); i++ {
// Если левый край текущего шара строго больше координаты стрелы,
// старая стрела физически не может его пробить.
if points[i][0] > end {
arrows++
// Выпускаем новую стрелу в правый край нового шара
end = points[i][1]
}
// Иначе шар пробивается уже летящей стрелой (points[i][0] <= end)
}
return arrows
}
5. Теоретический мост: Теорема Кёнига и дуальность интервалов
Обратите внимание на поразительное сходство между тремя задачами:
- Interval Scheduling: найти максимальный размер множества попарно непересекающихся отрезков.
- Non-overlapping Intervals: удалить минимальное число отрезков, чтобы оставшиеся не пересекались.
- Minimum Number of Arrows: найти минимальное число точек, прокалывающих все отрезки.
В математике и теории графов интервалов (Interval Graphs) существует фундаментальный результат — теорема о минимальном вершинном покрытии (Dilworth / Kőnig theorem):
Размер максимального независимого множества (максимум непересекающихся отрезков) в графе интервалов в точности равен минимальному размеру покрытия отрезков точками (минимальному числу стрел)!
Каждая стрела пробивает свою независимую группу интервалов. Если существует $K$ непересекающихся отрезков, то ни одна стрела не может пробить одновременно два из них, следовательно, стрел требуется как минимум $K$. Наш жадный алгоритм находит ровно $K$ точек.
6. Mechanical Sympathy и Highload-оптимизации
- In-place сортировка:
slices.SortFuncпереставляет элементы входного слайса без выделения дополнительной памяти в куче (0 allocs/op). - Кэш-локальность: После сортировки алгоритм совершает строго последовательный обход массива. Аппаратный префетчер процессора (Hardware Stream Prefetcher) заранее подгружает следующие кэш-линии из L2/L3 в L1D, сводя задержки доступа к данным к нулю.
- Регистровая оптимизация ABIInternal: Переменные
arrowsиendполностью размещаются в регистрах процессора (например,RAXиRBX), цикл не обращается к стеку.
7. Вопросы для собеседования
Итог кластера «Жадные алгоритмы»
За этот кластер мы детально изучили ключевые парадигмы жадных алгоритмов:
- Интервальное планирование: Сортировка по времени окончания максимизирует оставшееся окно возможностей.
- Кумулятивный баланс: Решение задачи о заправках (5. Gas Station) через инвариант замкнутого контура.
- Прыжки и охват: Динамическое расширение горизонта событий в 3. Jump Game и 4. Jump Game II.
- Разрешение конфликтов: Использование математической инверсии и теоремы о покрытии точками.
Мы завершили фундаментальный разбор жадных стратегий. Теперь мы переходим к мощнейшему аппарату алгоритмической оптимизации, решающему задачи там, где локальная жадность бессильна, — Динамическому программированию.
В следующей лекции мы заложим теоретический фундамент одномерного ДП: состояния, переходы, мемоизация и сведение памяти к $O(1)$: 1. Теория. Динамическое программирование 1D.