一、題目大意
標簽: 貪心
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons
有一些球形氣球貼在一堵用 XY 平面表示的墻面上，墻面上的氣球記錄在整數陣列 points ，其中points[i] = [xstart, xend] 表示水平直徑在 xstart 和 xend之間的氣球，你不知道氣球的確切 y 坐標，
一支弓箭可以沿著 x 軸從不同點 完全垂直 地射出，在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 xstart，xend， 且滿足 xstart ≤ x ≤ xend，則該氣球會被 引爆 ，可以射出的弓箭的數量 沒有限制 ， 弓箭一旦被射出之后，可以無限地前進，
給你一個陣列 points ，回傳引爆所有氣球所必須射出的 最小 弓箭數 ，
示例 1：
輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
解釋：氣球可以用2支箭來爆破:
-在x = 6處射出箭，擊破氣球[2,8]和[1,6]，
-在x = 11處發射箭，擊破氣球[10,16]和[7,12]，
示例 2：
輸入：points = [[1,2],[3,4],[5,6],[7,8]]
輸出：4
解釋：每個氣球需要射出一支箭，總共需要4支箭，
示例 3：
輸入：points = [[1,2],[2,3],[3,4],[4,5]]
輸出：2
解釋：氣球可以用2支箭來爆破:
- 在x = 2處發射箭，擊破氣球[1,2]和[2,3]，
- 在x = 4處射出箭，擊破氣球[3,4]和[4,5]，
提示:
- 1 <= points.length <= 105
- points[i].length == 2
- -231 <= xstart < xend <= 231 - 1
二、解題思路
區間重疊問題，一般都要想到貪心（區域最優等于全域最優），本題給我們一堆大小不等的氣球，用區間范圍來表示氣球大小，可能會有重疊區間，我們用最少的箭打爆所有氣球，我們把所有區間按照右邊界進行排序，因為每個氣球都要被打破，因此排序得到的第一組資料我們一定要使用，只要沿著該資料最右邊界的位置進行射箭一定能打破盡可能多的氣球，然后依次移動射箭的位置，進行統計即可，
三、解題方法
3.1 Java實作
public class Solution {
public int findMinArrowShots(int[][] points) {
// 二維陣列的排序？？
Arrays.sort(points, Comparator.comparingInt(o -> o[1]));
int res = 1;
int end = points[0][1];
for (int i = 1; i < points.length; i++) {
if (points[i][0] <= end) {
end = Math.min(end, points[i][1]);
} else {
res++;
end = points[i][1];
}
}
return res;
}
}
四、總結小記
- 2022/7/27 恢復每日一題
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500421.html
標籤：其他
上一篇：樹狀陣列