435. Non-overlapping Intervals
2021-02-06 本文已影响0人
morningstarwang
Ref: https://leetcode-cn.com/problems/non-overlapping-intervals/
这道题的思路是考虑以何种顺序遍历全部区间,使得去除最少的区间数目以实现其他区间均无重叠。直观上看,可以以每个为key,对整个进行升序排序。同时,维护当前遍历区间的前一个区间的右边界为,当当前的区间时,可以认为当前区间应当remove,故计数加一。直到遍历全部的区间后,可以返回最小的remove结果。代码实现如下:
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
n = len(intervals)
if n == 0:
return 0
intervals.sort(key=lambda x: x[1])
result = 0
prev = intervals[0][1]
for i in range(1, n):
if intervals[i][0] < prev:
result += 1
else:
prev = intervals[i][1]
return result