题目描述：
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
数据范围：
$1\le points.len \le 10^5$
题解：
分组循环：使用双层循环，外层枚举起点，内层枚举终点
1
2
3
4
5
6
7
8
9
| int i = 0, j;
while(l < n)
{
j = i + 1;
while(j < n && 满足条件) ++j;
i = j;
}
|
代码：
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
32
33
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int findMinArrowShots(vector<vector<int>> &points)
{
int n = points.size();
sort(points.begin(), points.end(), [](const vector<int> &a, const vector<int> &b)
{ return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0]; });
int ans = 0;
int i = 0;
while (i < n)
{
int j = i + 1;
while (j < n && points[j][0] <= points[i][1])
{
++j;
}
ans++;
i = j;
}
return ans;
}
};
|