tags: LeetCode,Python3,Medium

452. Minimum Number of Arrows to Burst Balloons

題目連結： Minimum Number of Arrows to Burst Balloons

解題方向

• points參數為二維陣列，每個子陣列都代表一個圓型氣球的最左及最右的x軸位置（直徑）
• 若你可以選定一個x位置投擲箭矢射中氣球則arrows+1，本題要求使用「最少數量」的箭矢
• 排序：
  • 先講二維陣列以子陣列的第一個值來進行由小到大排序
• 貪婪法：
  • 從第一個氣球開始，射出一箭，然後看看這支箭能射中多少氣球
  • 檢查下一個氣球的起始位置是否在目前箭能達到的最遠距離內（即前一個氣球的結束位置）
  • 如果是，那麼這個氣球也可以被目前這支箭射中。
  • 我們更新能被這支箭射中的氣球的最遠距離為「當前氣球的結束位置和已射中的氣球的最遠距離的最小值」（更新end值）
  • 如果不是，我們就需要另外一支箭，然後繼續重複此演算法（當作end值替換為目前氣球右邊的x）

完整程式碼

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x:x[0])
        arrows=1
        end=points[0][1]
        for b in points[1:]:
            if b[0]>end:
                arrows+=1
                end=b[1]
            else:
                end=min(end,b[1])
        return arrows