给定一堆的线段范围,每个线段i从points[i][0]~points[i][1],每次射击某一个值p,若points[i][0]<=p<=points[i][1]的线段可以被消除,问一共需要射击几次可以消除所有线段。贪心
先对这个二维point list按第二维的值从小到大排序,然后从第一根线段开始,射击最右端的点,之后的线段若可以cover这个点,则一并被消去
1 #452
2 #Runtime: 2320 ms (Beats 46.75%)
3 #Memory: 62.9 MB (Beats 34.32%)
4
5 class Solution(object):
6 def findMinArrowShots(self, points):
7 """
8 :type points: List[List[int]]
9 :rtype: int
10 """
11 pt_sorted = sorted(points, key = (lambda x:[x[1], x[0]]))
12 ans = 0
13 i = 0
14 while i < len(pt_sorted):
15 p = pt_sorted[i][1]
16 while i < len(pt_sorted) and pt_sorted[i][0] <= p <= pt_sorted[i][1]:
17 i += 1
18 ans += 1
19 return ans