算法练习Day27 （Leetcode/Python-贪心算法）

452. Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array?points?where?points[i] = [xstart, xend]?denotes a balloon whose?horizontal diameter?stretches between?xstart?and?xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up?directly vertically?(in the positive y-direction) from different points along the x-axis. A balloon with?xstart?and?xend?is?burst?by an arrow shot at?x?if?xstart <= x <= xend. There is?no limit?to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array?points, return?the?minimum?number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

思路：最少多少剑射穿气球。

先对气球按照一边的大小进行排序。若按照左边界，那么当前气球的左边界如果大于之前累积的气球的右边界，就必须得加一支箭才可以射穿当前气球了。

以这个思路，更详细分析就是要记录当前累计气球的交集，也就是在哪个范围内当前箭可射穿当前累计的所有气球。若气球1是[2,5], 气球2是[3,6], 那么这个交集的区间是[3,5], 左边界是3，右边界是5，如果新来的气球的左边界大于了5，那么就无法用同一支箭射穿了。这种情况下，写法上可以选择更新原气球数组，每次都把当前气球i的左右边界更新为当前箭可射穿的左右边界，如果下一个气球i依然可以被同一支箭射穿，那就继续更新下一个气球的右边界，否则就不更新了，算是新一支箭的左右边界。另一种不更新原数组的写法就是记录当前箭的左右边界。

不过注意了，更简化的算法是只更新右边界就可以了，左边界的更新是冗余的。因为排过序，新的左边界肯定大于旧的左边界，所以只要新的左边界小于旧的右边界，左边界就一定是落在原来区间的，反之则不然。

另外要注意的一点是xstart <= x <= xend就可以射穿，这里是闭区间，所以判断是否需要一支新箭时，取的是右边界大于之前的左边界时才要换，而不是大于等于。

还有写法上如果涉及i-1，for循环序号就要注意从1开始。那么序号为0的情况就要特别处理，或可考虑作为初始化。

class Solution(object):
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        """
        if len(points) == 0: return 0
        points.sort(key = lambda x: x[0])
        result = 1
        for i in range(1,len(points)):
            if points[i][0]>points[i-1][1]:
                result += 1 
            else:
                points[i][1] = min(points[i-1][1], points[i][1])
        return result
        """
        points.sort(key = lambda x:x[0])
        sl, sr = points[0][0], points[0][1] # use sl and sr to record the left and right boundary of the current interval separately.
        count = 1
        for i in points:
            if i[0] > sr: # if the left boundary of this balloons is out of current interval, we need a now arrow. 
                count += 1
                sl, sr = i[0], i[1] #注意，不仅仅是右边界要更新，左边界也是要更新的！！
            else:
                sl = max(sl, i[0]) # 不要搞错了min和max，这里要的是区间的交集不是并集
                sr = min(sr, i[1])
        return count