Minimum Number of Arrows to Burst Balloons (M)
题目
There are some spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter, and hence the x-coordinates of start and end of the diameter suffice. The start is always smaller than the end.
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps traveling up infinitely.
Given an array points where points[i] = [xstart, xend], return the minimum number of arrows that must be shot to burst all balloons.
Example 1:
Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
Example 2:
Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Example 3:
Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Example 4:
Input: points = [[1,2]]
Output: 1
Example 5:
Input: points = [[2,3],[2,3]]
Output: 1
Constraints:
0 <= points.length <= 104points.length == 2-231 <= xstart < xend <= 231 - 1
题意
给定若干个宽度为一个区间的气球，问最少多少箭能射穿所有气球。
思路
贪心问题，先将区间按照左端点(相同则右端点)升序排列，遍历所有区间，如果两个区间相交，说明可以一箭同时射穿这两个区间，而射箭的位置定位两区间中较小的右端点以尽可能射到更多的区间，每次判断相交时都以上一次的射箭位置为右端点进行判断；如果不相交，说明需要多射一箭。
代码实现
Java
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) {
return 0;
}
Arrays.sort(points, (a, b) -> a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : a[1] < b[1] ? -1 : a[1] > b[1] ? 1 : 0);
int ans = 1;
int end = points[0][1];
for (int i = 1; i < points.length; i++) {
int[] point = points[i];
if (point[0] <= end) {
end = Math.min(end, point[1]);
} else {
ans++;
end = point[1];
}
}
return ans;
}
}