452.用最少数量的箭引爆气球(Medium)

题目描述

在一个水平方向上，有一堆气球，现在给出气球直径的起点和终点，问最少需要多少箭能把所有气球引爆。

样例

Input: [[10,16],[2,8],[1,6],[7,12]]
Output: 2
# x=6,11 射出两根箭能把所有气球引爆

题解

本题和435无重叠区间思路一致，区别在于当交叉的时候，箭的数量并不变，而不交叉的时候，需要射出新的箭，并更新箭的位置

代码示例

Python 示例

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points: return 0
        points.sort(key=lambda x: x[1])
        end = points[0][1]
        arrow = 1
        for idx in range(1, len(points)):
            if points[idx][0] <= end: # 有交叉
                pass
            else: # 无交叉
                arrow += 1
                end = points[idx][1]
        return arrow

Go 示例

func findMinArrowShots(points [][]int) int {
    n := len(points)
    if n == 0 { return 0}
    sort.Slice(points, func(i, j int) bool {
        return points[i][1] < points[j][1]
    })
    end := points[0][1]
    arrow := 1  // 默认只有一根箭
    for i := 1; i < n; i++ {
        if points[i][0] <= end {  // 存在交叉
            ; // 啥也不做
        } else {  // 无交叉
            arrow++
            end = points[i][1]
        }
    }
    return arrow
}