当前位置： 面试刷题>> 用最少数量的箭引爆气球(经典算法150题)
### 题目描述
在一条直线上，有`n`个气球排列着，每个气球都有一个水平位置`x`和一个半径`r`，表示气球的中心位于`x`且其覆盖的区间是`[x-r, x+r]`。现在，你有一支箭，可以水平地射向任意位置，箭一旦射出就会贯穿所有在其路径上的气球（即气球的中心位于箭的路径上或气球被箭的半径所覆盖）。请问，你至少需要射出多少支箭才能引爆所有气球？
### 示例
假设有`n = 6`个气球，其位置和半径如下：
```
[[10,5],[16,2],[2,8],[1,6],[7,2],[12,1]]
```
- 第一个气球：[10,5]，覆盖区间是[5, 15]
- 第二个气球：[16,2]，覆盖区间是[14, 18]
- 第三个气球：[2,8]，覆盖区间是[-6, 10]
- 第四个气球：[1,6]，覆盖区间是[-5, 7]
- 第五个气球：[7,2]，覆盖区间是[5, 9]
- 第六个气球：[12,1]，覆盖区间是[11, 13]
在这个例子中，我们至少需要射两支箭来引爆所有气球。第一支箭射在`x=6`的位置（或任何[5,7]之间的位置），引爆第三、第四个和第五个气球；第二支箭射在`x=14`的位置（或任何[14,15]之间的位置），引爆第一个和第二个气球。第六个气球由于不与任何已引爆的气球重叠，需要单独一支箭来引爆，但由于它已经被第一支箭的路径所覆盖，因此实际上不需要额外的箭。
### 解题思路
这个问题可以通过贪心算法来解决。首先，我们需要根据气球的结束位置（即`x+r`）进行排序，因为如果两个气球的结束位置相近，那么它们的引爆位置可能相同，这样可以同时引爆多个气球。然后，我们遍历排序后的气球数组，尽量将箭射在能引爆最多气球的位置（即当前气球的开始位置，因为它是在当前考虑的气球中结束位置最早的）。
### PHP 代码示例
```php
function findMinArrowShots($points) {
if (empty($points)) return 0;
// 根据气球的结束位置排序
usort($points, function($a, $b) {
return $a[0] + $a[1] <=> $b[0] + $b[1];
});
$count = 1; // 至少需要一支箭
$end = $points[0][0] + $points[0][1]; // 当前箭的结束位置
for ($i = 1; $i < count($points); $i++) {
if ($points[$i][0] > $end) {
// 如果当前气球的开始位置大于当前箭的结束位置，则需要新箭
$count++;
$end = $points[$i][0] + $points[$i][1];
}
}
return $count;
}
// 示例
$balloons = [[10,5],[16,2],[2,8],[1,6],[7,2],[12,1]];
echo findMinArrowShots($balloons); // 输出 2
```
### Python 代码示例
```python
def findMinArrowShots(points):
if not points:
return 0
# 根据气球的结束位置排序
points.sort(key=lambda x: x[0] + x[1])
count = 1
end = points[0][0] + points[0][1]
for i in range(1, len(points)):
if points[i][0] > end:
count += 1
end = points[i][0] + points[i][1]
return count
# 示例
balloons = [[10,5],[16,2],[2,8],[1,6],[7,2],[12,1]]
print(findMinArrowShots(balloons)) # 输出 2
```
### JavaScript 代码示例
```javascript
function findMinArrowShots(points) {
if (points.length === 0) return 0;
// 根据气球的结束位置排序
points.sort((a, b) => a[0] + a[1] - (b[0] + b[1]));
let count = 1;
let end = points[0][0] + points[0][1];
for (let i = 1; i < points.length; i++) {
if (points[i][0] > end) {
count++;
end = points[i][0] + points[i][1];
}
}
return count;
}
// 示例
const balloons = [[10,5],[16,2],[2,8],[1,6],[7,2],[12,1]];
console.log(findMinArrowShots(balloons)); // 输出 2
```
以上代码均实现了用最少数量的箭引爆气球的问题，并给出了PHP、Python和JavaScript的示例实现。