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

## 问题描述
[452.用最少数量的箭引爆气球](https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/)

## 解题思路
首先，按照$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])`。

## 代码
```cpp
#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;
    }
};
```