第五天——贪心算法——射气球

1.题目

有一些球形气球贴在一个表示 XY 平面的平坦墙壁上。气球用一个二维整数数组 points 表示，其中 points[i] = [xstart, xend] 表示第 i 个气球的水平直径范围从 xstart 到 xend。你并不知道这些气球的具体 y 坐标。

可以从 x 轴上的不同位置垂直向上（即 y 轴正方向）射出箭。如果某一箭的 x 坐标 x 满足 xstart <= x <= xend，则这支箭可以射爆对应的气球。射出的箭没有数量限制，并且一旦射出，箭会一直向上飞行，可以射穿沿途的所有气球。

给出气球的二维数组，求最少需要多少支箭射爆所有气球？

2.分析

这实际上是一个区间覆盖问题（Interval Covering Problem），类似于：

• 经典例题：给定多个区间，如何用最少的点覆盖所有区间？（每个区间至少包含一个点）
• 解法思路：
  • 贪心算法：按区间右端点排序，尽量在右端点射箭，以覆盖尽可能多的区间。

解题步骤

1. 排序：
   • 将所有区间按照 xend（右端点）升序排序。
2. 贪心选择：
   • 初始化 count = 0（记录需要的箭的数量），并设 last_shot = -∞（上一次射箭的位置）。
   • 遍历排序后的区间：
   • 如果当前区间的 xstart > last_shot（说明无法被上一箭覆盖）：
   • count += 1，并更新 last_shot = xend。
   • 射一支新箭，位置选在当前区间的 xend（保证覆盖最多的区间）。
3. 返回 count：
   • 最终 count 就是最少需要的箭数。

3. 完整代码

def findMinArrowShots(points):
    if not points:
        return 0
    
    # 按 xend 排序
    points.sort(key=lambda x: x[1])
    
    count = 1
    last_shot = points[0][1]   # 第一箭射在第一个气球的右端点
    
    for start, end in points:
        # 如果当前气球未被上一箭覆盖，则射新箭
        if start > last_shot:
            # 需要新射一箭
            count += 1
            last_shot = end  
    return count
print(findMinArrowShots([[10,16],[2,8],[1,6],[7,12]]))  # Output: 2

解释

1. 输入 [[10,16],[2,8],[1,6],[7,12]]：

   • 排序后 [[1,6], [2,8], [7,12], [10,16]]
   • 第一箭射 6（覆盖 [1,6],[2,8]）
   • 第二箭射 12（覆盖 [7,12],[10,16]）
   • 最少需 2 箭 ✅