LeetCode 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 10⁴ balloons. An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x_start and x_end bursts by an arrow shot at x if x_start ≤ x ≤ x_end. 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).

---

平面上（可以看成是直线上）摆了很多个气球，气球有长度，占据了[s,t]的位置，气球之间可能会有重叠，现问最少用多少支箭能把所有气球射穿。 我们肯定希望把箭射在重叠气球最多的区域，但是不和其他气球重叠的气球终究要被射穿。我们可以采用贪心的策略，气球的区域用pair存储了，我们对所有气球的pair排序，得到先按start排序，再按end排序的一系列气球。 然后我们贪心的求重叠气球最多的区域，对于第一个气球，我们可以射[s1,t1]，如果第二个气球的区域[s2,t2]和[s1,t1]有重叠，即s2<=t1，则这一箭可以射在重叠的区域，即[max(s1,s2),min(t1,t2)]，我们再看第三个气球是否和[max(s1,s2),min(t1,t2)]有重叠，有的话又可以一箭三雕，此时又要更新重叠区域，如此循环下去。 具体怎样实现好呢，我们用end来记录当前重叠区域的结束位置。因为已经按pair排序了，如果后面气球的s小于等于前面重叠区域的end，则后面气球肯定会和重叠区域重叠，此时我们还需要更新新的重叠区域的end为之前的end和后面气球的t的最小值。这样相当于重叠区域在一步步收窄。当某个气球的s不再小于等于end时，前一个贪心阶段结束，需要新开一个重叠区域。 完整代码如下： [cpp] class Solution { public: int findMinArrowShots(vector<pair<int, int>>& points) { if (points.size() == 0)return 0; sort(points.begin(), points.end()); int i = 0, j = 1, end, ans = 0; while (i < points.size()) { end = points[i].second; while (j < points.size() && points[j].first <= end) { end = min(end, points[j].second); ++j; } ++ans; i = j++; } return ans; } }; [/cpp] 本代码提交AC，用时445MS。 参考：http://www.cnblogs.com/grandyang/p/6050562.html]]>