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