在二維空間中有許多球形的氣球，對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結束坐標，由于它是水平的，所以縱坐標并不重要，因此只要知道開始和結束的橫坐標就足夠了，開始坐標總是小于結束坐標，
一支弓箭可以沿著 x 軸從不同點完全垂直地射出，在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 xstart，xend， 且滿足 xstart ≤ x ≤ xend，則該氣球會被引爆，可以射出的弓箭的數量沒有限制， 弓箭一旦被射出之后，可以無限地前進，我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數量，
給你一個陣列 points ，其中 points [i] = [xstart,xend] ，回傳引爆所有氣球所必須射出的最小弓箭數，
示例 1：
輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
解釋：對于該樣例，x = 6 可以射爆 [2,8],[1,6] 兩個氣球，以及 x = 11 射爆另外兩個氣球
示例 2：
輸入：points = [[1,2],[3,4],[5,6],[7,8]]
輸出：4
示例 3：
輸入：points = [[1,2],[2,3],[3,4],[4,5]]
輸出：2
示例 4：
輸入：points = [[1,2]]
輸出：1
示例 5：
輸入：points = [[2,3],[2,3]]
輸出：1
提示：
0 <= points.length <= 104
points[i].length == 2
-231 <= xstart < xend <= 231 - 1
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons
class Solution(object):
def findMinArrowShots(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
if points==[]:
return 0
points.sort()
left,right=points[0][0],points[0][1] #以第一個數的左右端點為起止點
arrow=1
for i in points[1::]:
left = i[0]
if left > right:
arrow += 1
right = i[1]
else:
if i[1] < right:
right = i[1]
return arrow
解題思路
我用的start排序，所以先說start排序：主要思路是如果兩個區間完全不挨著，那肯定得多用一根箭；如果兩個區間挨著就不用多加一根，但3個及以上區間挨著時就一定要注意挨著的這些區間的最小end，如果下一個區間的start大于這個最小end，那即使區間挨著也得多加一根箭，兩個區間挨著的話肯定一根箭就夠了，3個及以上挨著可就不一定了，
Λ
[-------|]
[----|------] //這倆哥們一個箭夠了
[-|---------] //如果第三個是這樣的，那一根箭還是夠的
| [-------] //如果是這樣的呢，不行了，因為這個的start小于第一行那個end了，所以得再加一根
作者：hongyang57
鏈接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/solution/tan-xin-an-endpai-xu-bi-an-startpai-xu-yao-hao-by-/
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/226871.html
標籤：python
上一篇：通過python爬蟲爬取圖片，并通過企業微信機器人發送圖片至企業微信群
下一篇：k-近鄰（knn）演算法