作者:
Rushia (みけねこ的鼻屎)
2023-01-05 13:50:47※ 引述《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: