Re: [閒聊] 每日LeetCode
※ 引述《fxfxxxfxx (愛麗絲)》之銘言：
: 452. Minimum Number of Arrows to Burst Balloons
給你一個二維陣列points，points[i]={x1, x2}表示第i個氣球的水平座標，我們將
氣球依照水平座標重疊，假設我們開一槍可以貫穿一整排的氣球，求出我們最少要開
幾槍才可以把氣球都打爛。
Example：
Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: 氣球按照下列方式排成一列
[10 11 12 13 14 15 16]
[2 3 4 5 6 7 8]
[1 2 3 4 5 6]
[7 8 9 10 11 12]
我們第一次射擊射6位置可以打破points[1]和points[2]
第二次射擊可以打破points[0]和points[3]，最少共需要兩次射擊，所以返回2。
Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: 氣球按照下列方式排成一列
[1 2]
[3 4]
[5 6]
[7 8]
每個氣球不重疊，共需要四次射擊
思路：
1.一開始是想把points排序之後的每個區間合併然後算有多少個不交替的區間，
但是像是[1 2] [2 3] [3 4] 雖然可以合併但是其實需要射兩次，所以換個方
向思考。
2.我們把氣球的最右邊想像成「最晚必須要射擊的地方」，然後按照最右邊座標
排序，以 [[10,16],[2,8],[1,6],[7,12]] 來說，排序完之後長這樣：
[1 2 3 4 5 6]
[2 3 4 5 6 7 8]
[7 8 9 10 11 12]
[10 11 12 13 14 15 16]
3.我們從左到右一路射過去，每次都射擊當前氣球的最右邊，排序完之後可以明顯觀察到
你射最右邊的同時會射到其他氣球的左邊部分，遇到小於的就表示重疊了該個氣球可跳
過，而當左邊的座標小於下一個氣球的右邊座標的時候，表示後面沒有氣球了，下一次
的射擊位置將改為下個氣球的最右邊，重複動作直到氣球射完為止。
Java Code：
------------------------------------------
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, Comparator.comparingInt(a -> a[1]));
int count = 1;
int end = points[0][1];
for (int[] point : points) {
if (point[0] > end) {
count++;
end = point[1];
}
}
return count;
}
}
------------------------------------------
--
https://i.imgur.com/PIoxddO.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.71.48 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672897850.A.117.html
※ 編輯: Rushia (1.160.71.48 臺灣), 01/05/2023 13:54:53
推
01/05 23:52,
2年前
, 1F
01/05 23:52, 1F
推
01/06 00:09,
2年前
, 2F
01/06 00:09, 2F
→
01/06 00:09,
2年前
, 3F
01/06 00:09, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 180 之 719 篇)：