leetcode 452 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 xendbursts 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).

总的来说，就是在水平方向上🏹，用最少的箭射吧全部的区间射掉。

先按数组中的第一个元素对区间排序

设定一个当前一箭能够着的最高的位置

遍历每一个区间，如果当前区间的开始点大于当前一箭能够着的最高点，就说明当前这个区间需要再用一把箭，ans ++，且令下一把箭能够够着的最高点设为当前区间的结束点。

如果当前区间的开始点小于前一箭能够够着的最高点，说明前一把箭能够射中当前区间，此时需要更新前一把在保证射掉当前区间的同时，能够够着的最高点，也就是需要比较前一把箭的最高点和当前区间的结束点的位置，如果当前区间结束点的位置要小于前一把箭的最高点，则将前一把箭的组高点设为当前区间的结束点。

class Solution(object):
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        points = sorted(points, key=lambda x:x[0])
        highest = -float('inf')
        ans = 0
        for start, end in points:
            if highest < start:
                ans += 1
                highest = end
            elif highest > end:
                highest = end
        return ans