【PPT解leetcode 452】射击气球_leetcode ppt

1.排序

使用sort(points.begin(),points.end())；默认是对二维数组第一列进行升序排列，即气球的左坐标从小到大排列，并且将shoot_end初始化为第一个气球的右坐标。

接下来对后面每个气球进行遍历，比较第i个气球的左边界和是否小于shoot_end（第一次比较end_shoot即为0气球的右坐标）

2.接下来有两种情况

第一种是，新气球的左边界的坐标大于shoot_end，这时候表明，需要增加一个枪手，并且需要更新shoot_end为新气球的右坐标；图示为1号气球的左坐标大于shoot_end，此时代表需要增加一个枪手，并且再将1号气球的右坐标作为shoot_end。

第二种情况是不需要新添枪手，即新气球的左坐标，小于shoot_end，表明两个气球有重叠区域，这时候仅需要更新shoot_end即可，新shoot_end为重叠区域的右坐标，即
min(shoot_end,points[i][1])


更新shoot_end为重叠区域的右坐标

完整代码

class Solution {
public:

    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size()==0)
        {
            return 0;
        }
        std::sort(points.begin(),points.end());
        //sort()函数，默认的是对二维数组按照第一列进行排序。VIA[i][0],这一列。
        int shoot_end=points[0][1];
        int shoot_num=1;
        for(int i=1;i<points.size();i++)
        {
            if(points[i][0]>shoot_end)
            {
                shoot_num++;
                shoot_end=points[i][1];
            }
            else
            {
                shoot_end=min(shoot_end,points[i][1]);
            }

        }
        return shoot_num;

    }
};
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