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