Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定一堆的线段范围,每个线段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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理