1232 · 爆破气球的最小箭头数

描述

在二维空间中有许多球形气球。 对于每个气球，提供的输入是水平直径的起点和终点坐标。 由于它是水平的，因此y坐标无关紧要，因此直径的起点和终点的x坐标就足够了。 起点总是小于终点。 最多将有10^4个气球。

可以沿x轴从不同点垂直向上发射箭头。 如果xstart≤x≤xend，则坐标为xstart和xend的气球被在x处发射的箭头戳爆。 可以发射的箭头数量没有限制。 一次射击的箭头一直无限地向上移动。 问题是要找到戳破所有气球的最小发射箭头数。

---

 

样例1

输入:
[[10,16], [2,8], [1,6], [7,12]]
输出:
2
说明：
一种方法是发射一个箭头，例如在x = 6（爆破气球[2,8]和[1,6]），发射另一个箭头在x = 11（爆破其他两个气球）。

样例2

输入:
[[1,2],[3,4],[5,6],[7,8]]
输出:
4

 

    int findMinArrowShots(vector<vector<int>> &points) {

        // Write your code here

        if(0 == points.size())

        {

            return 0;

        }

        sort(points.begin(),points.end(),cmp);

        int count=1;

        int x=points[0][1];

        for(int i=1;i<points.size();i++)

        {

            if(x < points[i][0])

            {

                x= points[i][1];

                count++;

            }

        }

        return count;

 

    }