题目:
给你一串气球阵列
用垂直x轴的箭射破他们
擦到边就可以了
问你最少要几只箭矢
直接举例说明比较快= =
[[1,3][3,7][10,11][10,12]]
这里的气球需要两只箭
射过3跟11
就可以射破全部气球了
解法:
反正都要看气球
就先排序好了
排序之后
一次射一只箭矢
一只箭矢能破坏掉所有重叠的气球当然最好
所以就一直往右边找
直到没办法再一次射破更多
就换下一只箭矢
然后
对ㄚ= =
```cpp
class Solution {
public:
static bool compare(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points)
{
sort(points.begin(), points.end(), compare);
int len = points.size();
int res = 0;
int lp = 0;
int rp = 0;
for(int i = 0 ; i < len ;)
{
res ++;
lp = points[i][0];
rp = points[i][1];
i++;
while(i<len)
{
if(points[i][0] > rp)
{
break;
}
else if(points[i][0] == rp)
{
while(i < len && points[i][0] == rp)
{
i ++;
}
break;
}
else if(points[i][0] > lp)
{
lp = points[i][0];
}
if(points[i][1] < rp)
{
rp = points[i][1];
}
if(lp == rp)
{
while(i < len && points[i][0] == rp)
{
i ++;
}
break;
}
i++;
}
}
// for(auto k : points)
// {
// cout << "[" << k[0] << "," << k[1] << "]" ;
// }
return res;
}
};
```