Posted on 2023-07-19 17:22
Uriel 閱讀(46)
評論(0) 編輯 收藏 引用 所屬分類:
貪心 、
閑來無事重切Leet Code
給出一些intervals的開始和結束點，問最少去掉幾個interval可以保證剩下的intervals沒有overlap，貪心思路，先給intervals排序（先按開始節點排，相同的話按結束節點排），之后依次處理，如果當前的interval開始節點大于前一個結束節點，那這一interval不能去掉，否則去掉當前interval并且更新結束節點
1 #435
2 #Runtime: 1421 ms (Beats 25.19%)
3 #Memory: 59.8 MB (Beats 44.83%)
4
5 class Solution(object):
6 def eraseOverlapIntervals(self, intervals):
7 """
8 :type intervals: List[List[int]]
9 :rtype: int
10 """
11 intervals.sort()
12 ans = 0
13 pre = intervals[0][1]
14 for st, ed in intervals[1:]:
15 if st >= pre:
16 pre = ed
17 else:
18 ans += 1
19 pre = min(ed, pre)
20 return ans