LeetCode 452 - Minimum Number of Arrows to Burst Balloons

作者 QIFAN 日期 2016-12-30
LeetCode 452 - Minimum Number of Arrows to Burst Balloons

原题链接:452. Minimum Number of Arrows to Burst Balloons


题目

有一堆气球分散在二维坐标里,给出每个气球的左边界与右边界(x 轴),求最少能将所有气球打掉的箭的数量。

举例:

输入:
[[10,16], [2,8], [1,6], [7,12]]

输出:
2

解释:
这四个气球在坐标轴上是不相交的两部分,{[2,8],[1,6]} 和 {[10.16],[7,12]},所以最少需要两支箭才能把所有气球打掉。

思路

由于不考虑 y 值,所以简单的可以看成线段相交。

由于给定数组是乱序的,一般都会先试一试排序(恩看了一下并没有时间复杂度的要求)。所以先按第一个(起始横坐标)排序,再按第二个(收尾横坐标)。想象一下,将这些坐标投射到一条直线上,如果我们想要一箭射穿,那这些范围一定有一段共同的交汇。没有重合的线段一定要分两次。因此,问题就变成了找交汇。用例子来说明。

第一个线段:$(x_1, x_1’)$ ,此时交汇范围为 $(x_1, x_1’)$
第二条线段:$(x_2, x_2’)$,由于排序,所以 $x_1 < x_2$ 。
case 1: $x_2 > x_1’$ ,那第一条第二条就没有交点,需要的箭就多一根
case 2: $x_1 < x_2 < x_1$,那这两条线段有交点,从而我们需要确定交点的范围
case 2.1:$x_1’ < x_2’$ ,交汇范围为 $(x_2, x_1’)$
case 2.2:$x_1’ > x_2’$ ,交汇范围为 $(x_2, x_2’)$
再继续重复上面步骤,直到遍历所有线段。

时间复杂度: $nlogn$ (排序),$n$ (遍历)。因此为 $O(nlogn)$

代码:

public int findMinArrowShots(int[][] points) {
if (points == null || points.length == 0) {
return 0;
}
// 先按起始排序,再按终止排序
Arrays.sort(points, new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
if (o1[0] == o2[0]) {
return o1[1] - o2[1];
}
return o1[0] - o2[0];
}
});
int minArrows = 1;
// 左边坐标一定是增大的,可以只判断右边界限就好。
int rightBound = points[0][1];
for (int i = 1; i < points.length; i++) {
// 起始坐标落在交汇范围内,计算新的右界限
if (points[i][0] <= rightBound) {
rightBound = Math.min(rightBound, points[i][1]);
// 不在原交汇范围
} else {
minArrows++;
rightBound = points[i][1];
}
}
return minArrows;
}