【leetcode】452. Minimum Number of Arrows to Burst Balloons 解题报告

给定一个数组，数组中点元素都是包含两个元素的一维数组，分别表示一个气球的左右边界，求从水平线上垂直向上射箭，最多要几支箭才能把所有气球都射破。

思路

一支箭之所以能够射破多个气球是因为这些气球的横向坐标之间有重叠的部分，箭从重叠的部分射出就能同时穿破落在此位置的气球。所以这道题就是让所有气球尽可能的有重叠部分。
首先根据气球的左边坐标对数组进行排序，然后从左往右遍历，保存重叠的边界，如果遍历到一个新的元素，该气球不在前面重叠边界里时，说明该气球跟前面的气球没有相交部分，得用一支新的箭才能穿破，此时重新定义重叠边界。

class Solution:
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        from functools import  cmp_to_key
        points.sort(key = cmp_to_key(self.compare))
        res = 0
        index = 0
        while(index < len(points)):
            left = -float("inf")
            right = float("inf")
            while(index < len(points) and (left<=points[index][0]<=right or left<= points[index][1]<=right)):
                left = max(left,points[index][0])
                right = min(right,points[index][1])
                index +=1
            res +=1
        return res

    def compare(self,array1,array2):
        if array1[0] < array2[0]:
            return -1
        elif array1[0] == array2[0]:
            return 0
        else:
            return 1

可以优化一下上述代码，因为数组时按照气球左边界排好序的，所以每次遍历的时候，左边界都是不断往右更新的，我们只需要保存重叠区域的右边界即可，如果气球的左边界大于重叠区域的右边界，则重新开始。

class Solution:
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        if points ==[]:
            return 0
        points.sort(key =lambda x:x[0])
        # print(points)
        end = points[0][1]
        res = 0
        for i in points:
            if end < i[0]:
                res +=1
                end = i[1]
            else:
                end = min(end,i[1])
        return res+1