leetcode452 Minimum Number of Arrows to Burst Balloons(扎气球)

leetcode452 Minimum Number of Arrows to Burst Balloons(扎气球)


There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

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

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

题目的意思是说在空间内有一些气球,这里只考虑x轴的情况吧,那么这些球在x轴上有一个范围,是闭区间[a,b], 然后从上面扔针的话,可以一扎到底,输入是一些气球所在的区间,然后要输出最小的针数能够把所有的气球扎破。

想法

感觉这个题就像是之前做过的一个区间的合并的那个差不多的感觉,本质上相当于是要找到最少的族,在每一族中所有区间都相有公共的交集.

解法如下

class Solution(object):
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        if len(points)==0:
            return 0
        
        points = sorted(points, key=lambda x: x[0])
        
        ret = 1
        interval = points[0]
        for x in points[1:]:
            if interval[1] < x[0]:
                ret += 1
                interval = x
            else:
                interval=[max(interval[0],x[0]), min(interval[1], x[1])]
                
        return ret
        

意思是先将气球所在的区间从小到大排一个序,然后初始化一个interval,在这个区间内只有仍针就可以把之前的一批的给扎破,这是个贪心的算法,如果当前的这个区间和之前的那个区间如果没有交集的话,就更新interval,如果有交集,就把interval,更新成他们的交集。 注意最终要返回的结果ret要初始化为1才可以。也就是说这里面的interval实际上就是公共区间, 然后这个问题的本质是要把这些区间,分成具有公共区间的族,所以interval要不断地进行一个更新, 如果和之前的interval没有交集的话,就把针数加1.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦