Posted on 2023-07-19 17:22
Uriel 阅读(24)
评论(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