452.minimum-number-of-arrows-to-burst-balloons 用最少数量的箭引爆气球

问题描述

452.用最少数量的箭引爆气球

解题思路

首先，按照\(x_start\)从小到大的顺序排序，然后开始分析需要的弓箭数。

• if (points[i][0] > points[i - 1])，说明两个气球不存在重叠，需要两支箭，箭数result++;
• else，说明两个气球存在重叠，只需要一支箭，但此时，如何判断下一个气球是否需要新的箭呢:
  • if (points[i + 1][0] > min(points[i - 1][1], points[i][1]))，那么就需要新的箭，反之就不需要，因此，令points[i][1] = min(points[i - 1][1], points[i][1])。

代码

#include <algorithm>
#include <vector>
using std::sort;
using std::vector;
class Solution {
  private:
    static bool cmp(vector<int> &a, vector<int> &b) {
        return a[0] < b[0];
    }

  public:
    int findMinArrowShots(vector<vector<int>> &points) {
        int result = 1;
        sort(points.begin(), points.end(), cmp);
        for (int i = 1; i < points.size(); i++) {
            if (points[i - 1][1] < points[i][0])
                result++;
            else {
                points[i][1] = min(points[i][1], points[i - 1][1]);
            }
        }
        return result;
    }
};