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

维护一个射击区间。
如果下一个区间的开始位置比当前区间的开始位置大，则需要更新。
同理，结束位置也一样。

也是就是说，保持在这个射击区间内，每一个气球都能被射中（求射击区间内所有球的交集）。

如果气球不再能被这个射击区间所容纳，则在增加一个射击区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int findMinArrowShots(vector<pair<int, int>>& points) {
        if(points.size() == 0){
            return 0;
        }
        //对气球从左端点开始排序。
        sort(points.begin(),points.end());
        
        int arrow = 1;
        int startindex = points[0].first;
        int endindex = points[0].second;
        
        for(int i = 1; i < points.size(); i++){
            //更新最小区间。
            if(points[i].first > startindex && points[i].first <= endindex){
                startindex = points[i].first;
            }
            if(points[i].second < endindex && points[i].second >= startindex){
                endindex = points[i].second;
            }
            //继续下一轮。
            else if(points[i].first > startindex){
                startindex = points[i].first;
                endindex = points[i].second;
                arrow++;
            }
        }
        return arrow;
    }
};