Posted on 2023-07-19 17:22
Uriel 閱讀(43)
評論(0) 編輯 收藏 引用 所屬分類:
貪心 、
閑來無事重切Leet Code
給出一些intervals的開始和結(jié)束點，問最少去掉幾個interval可以保證剩下的intervals沒有overlap，貪心思路，先給intervals排序（先按開始節(jié)點排，相同的話按結(jié)束節(jié)點排），之后依次處理，如果當前的interval開始節(jié)點大于前一個結(jié)束節(jié)點，那這一interval不能去掉，否則去掉當前interval并且更新結(jié)束節(jié)點
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