用最少的箭引爆气球

题目描述

 &emps;在二维空间中散布着一些气球。对于每个气球，它们都是在同一水平直径上。所以对于纵坐标就没有那么重要了，x轴(横坐标)是气球的起点和终点，且起点始终小于终点。
  沿x轴不同的点会垂直向上射出一个箭头，如果Xstart<= x <= Xend，那么气球将会被箭射爆。根据输入的气球坐标，得到最少使用的箭数。

输入输出样例

  输入是一个数组，数组由多个气球的起始和终止坐标所组成。输出一个整数，表示所需最少的箭头数。

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

  在这个样例中，[1,6]与[2,8]重叠，[7,12]与[10,16]重叠，所以我们只需要两只箭就可以了

题解

  想要用最少的箭来射击最多的气球。那么就是说对于有重叠区间的气球，我们只需要安排一只箭射击就可以了。所以我们采取的贪心策略为，优先射击无重叠区域的气球
  具体实现方法为，先把这个数组进行std::sort排序(默认升序)，排序后的数组为[[1,6],[2,8],[7,12],[10,16]]。按照我们的贪心策略，在循环内初始化为[1,6]。查看与其重叠的区间，即第一个区间的终止位置可以覆盖接下来的起始位置。如果存在更小区间的气球，则更新prev并且对i进行自增。倘若条件不满足total 进行自增。

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end());
        int n = points.size();
        int total = 0,i = 0;
        while (i < n) {
            int prev = points[i][1];
            while (i < n && prev >= points[i][0]) {
                prev = min(points[i][1],prev);
                ++i;
            }
            ++total;
        }
        return total;
    }
};