↓Skip to main content
  1. Posts/

LeetCode-435 无重叠区间

·1 min·
Table of Contents

LeetCode-435 无重叠区间 #

Solution 1 #

按照右端点考虑区间, 如果当前的区间的左端点大于等于上一个区间的右端点, 则可以选择该区间, 否则删除该区间. 贪心地考虑, 删除该区间比删除上个区间更优.

代码如下:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key=lambda x: x[1])
        ans = len(intervals)
        cur_r = -inf
        for l, r in intervals:
            if l >= cur_r: # 保留该区间
                ans -= 1
                cur_r = r
        return ans

Solution 2 #

dp.

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        n = len(intervals)
        dp = [0] * n
        rs = [x[1] for x in intervals]
        for i in range(n):
            l_i = intervals[i][0]
            j = -1
            low, high = 0, i - 1
            while low <= high:
                mid = (low + high) // 2
                if intervals[mid][1] <= l_i:
                    j = mid
                    low = mid + 1
                else:
                    high = mid - 1
            dp[i] = max((0 if j < 0 else dp[j]) + 1, dp[i - 1])
        return n - dp[n - 1]