贪心想了半天,一直想不出完美的要解决条件,只知道要根据起点或终点排序。后来看了答案,原来是用总的区间数量减去没重复的区间数量,得到要去掉的区间数量。那就简单了,找出没重复的区间数量就好了,贪心,维护一段区间或者终点值就 ok 了。
class Solution(object):
def eraseOverlapIntervals(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: int
"""
if len(intervals) <= 1:
return 0
intervals.sort(key=lambda x: x[1])
end = intervals[0][1]
count = 1
for i in range(1, len(intervals)):
if intervals[i][0] >= end:
count += 1
end = intervals[i][1]
return len(intervals) - count
网友评论