题目描述

在一条直线上，有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 代码示例

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 代码示例

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 代码示例

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的示例实现。