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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/166807.html
標籤：其他
上一篇：線性表（三）：單鏈表的基本操作
下一篇：從上往下列印二叉樹