扎气球 2020-11-23（未允禁转）

给定一个 List[List[int]] ， 表示气球的分布。如

[[10,16],[2,8],[1,6],[7,12]]

其中的每个元素表示每个气球X轴上左右端点的位置[start, end]，如[10,16]表示该气球左边界为10，右边界为16
现在需要射箭戳破所有的气球，当射箭位置target满足

left_bound <= target <= right_bound

时，该气球被戳破。问最少需要射箭几次，才能戳破所有气球
原题：

leetcode 452. 用最少数量的箭引爆气球

我的思路：【模拟法-每一次都尽可能多地戳破气球】
1.将所有区间按左边界start排序
2.维护一个target_area，表示已遍历的区间的交集，射箭到这个区域内都会戳破之前的所有气球
3.从左到右遍历所有的区间，当target_area在当前区间内时，当前区间可以一起被戳破，求新的区间交集来更新target_area；当target_area不包含在当前区间内时，说明该气球需要新的一箭，那么结算之前的结果，并且更新target_area为current_ball区间

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # 假设n箭是最优解，那么n箭内部不存在先后关系
        # 1.排序points
        # 2.if target_area not in current_ball: res += 1 & target_area = current_ball
        # 3.else: narrow target_area
        points.sort()
        l = len(points)
        if l == 0:
            return 0
        target_area = points[0]
        res = 0
        for i in range(l):
            current_ball = points[i]
            if target_area[1] < current_ball[0]:
                res += 1
                target_area = current_ball
            else:
                target_area = [max(target_area[0], current_ball[0]), min(target_area[1], current_ball[1])]
            # 实时打印箭可以射的位置区间
            # print(target_area)
        # 记得加上最后一堆气球的一箭
        return res + 1

其实这是一种贪心思想，每次都尽可能一箭戳破更多的气球，直到下一气球不能被一箭戳破

引用一个leetcode评论：
「贪心」的思想体现在确定了求解空间，而不是盲目地枚举出所有可能的情况