贪心算法：力扣452. 用最少数量的箭引爆气球

1、题目描述：

2、题解：
贪心算法
首先，理解题意，多读几遍，题目说的是从x轴朝上射出箭，也即是垂直于x轴射箭。
先进行排序，然后出现下面的情况：

如果新的坐标的start也就是dp[i][0] > 上一个区间的end，也即是图中1的情况：那么箭的个数加1，更改end值；
否则，也就是2的情况，这种情况箭的数量不改变，只更新end值，以方便下次的判断。
        那么怎么更新end：end和points[i][1]作比较，两者较小的那个就是该end值，也就是end = min(end, points[i][1])
        
我们可以看一下情况3和情况4进行验证：
情况4：新的区间（也就是红色的区间）的start 比前面最小的end要大，那么新的区间需要一个新箭去射破，也即是箭的数量要加1
情况3：新的区间（也就是红色的区间）的start 比前面最小的end还小，那么可以只用一只箭就能完成任务

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        size = len(points)
        if size < 2:
            return size
        points.sort(key=lambda x: x[0])
        res = 1 #初始一定需要一只箭
        end = points[0][1]
        for i in range(1, size):
            if points[i][0] > end:
                res += 1
                end = points[i][1]
            else:
                end = min(end, points[i][1])
        return res

3、复杂度分析：
时间复杂度：O(NlogN)，排序的复杂度
空间复杂度：O(1)