问题描述
给定一个区间列表，每个区间表示气球直径的水平起点和终点，气球垂直分布在空间中，假设在某个位置垂直向上发射一支箭，如果箭经过气球所在水平坐标区间，则气球会被戳破。要求找出将所有气球戳破时需要最少的箭的数量。题目链接：**点我**
样例输入输出
输入：[[10,16], [2,8], [1,6], [7,12]]
输出：2
解释：在 2 的位置发射一支箭，可以戳破水平区间 [2, 8]、[1, 6] 的气球，在 10 的位置发射另一支箭，可以戳破 [10, 16]、[7, 12] 的气球
输入：[[1, 2], [2, 3], [3, 4], [4, 5]]
输出：2
解释：在 2 和 4 的位置发射箭
问题解法
将区间进行排序，然后遍历区间，取区间的交集。如果当前区间与上个交集的区间不存在交集的话，则说明需要另外发射一支箭，重新计算新的交集区间了。代码如下
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
| class Solution
{
public int findMinArrowShots(int[][] points)
{
if (points == null || points.length == 0)
{
return 0;
}
Arrays.sort(points, Comparator.comparingInt(point -> point[0]));
int prevEnd = points[0][1];
int count = 1;
for (int i = 1; i < points.length; i++)
{
if (points[i][0] < prevEnd)
{
prevEnd = Math.min(prevEnd, points[i][1]);
}
else if (points[i][0] > prevEnd)
{
prevEnd = points[i][1];
count++;
}
}
return count;
}
}
|