跳转至

435. 无重叠区间#

问题描述#

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

  1. 可以认为区间的终点总是大于它的起点。
  2. 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:


输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:


输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:


输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

解题思路#

从单独的每个区间来看，假设到了 \([\texttt{start}_i,\texttt{end}_i]\) 的最长不重叠区间数量为 \(\texttt{dp}[i]\)，那么

\(\texttt{dp}[i] = 1 + \max(\texttt{dp}[j])\) 并且 \(\texttt{end}_j\le\texttt{start}_i\)。

所以可以对 \(\texttt{intervals}\) 中的区间按照 \(\texttt{end}\) 的值从小到大排列（按照 \(\texttt{start}\) 也一样），然后对于每个区间 \(\texttt{intervals}[i]\) 遍历该区间之前的每个满足 \(\texttt{end}_j\le\texttt{start}_i\) 的区间取最大值即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        intervals.sort(key=lambda x: x[1])
        n = len(intervals)
        dp = [1] * n
        ans = 1
        for i in range(1, n):
            t = 0
            for j in range(i):
                if intervals[j][1] <= intervals[i][0] and dp[j] > t:
                    t = dp[j]
            dp[i] += t
            ans = max(ans ,dp[i])
        return n - ans

实际上，对于 \(\texttt{intervals}[i]\) 来说，让 \(\texttt{dp}[i]\) 取得最大值的区间，应该是在所有的 \(\texttt{end}_j\le\texttt{start}_i\) 的区间中选择 \(\texttt{start}_j\) 最大的区间。

这样我们可以对 \(\texttt{intervals}\) 中的区间按照 \(\texttt{start}\) 的值从小到大排列，然后对于 \(\texttt{intervals}[i]\)，从后往前遍历得到第一个满足 \(\texttt{end}_j\le\texttt{start}_i\) 的区间即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        intervals.sort(key=lambda x: x[0])
        n = len(intervals)
        dp = [1] * n
        ans = 1
        for i in range(1, n):
            for j in range(i - 1, -1, -1):
                if intervals[j][1] <= intervals[i][0]:
                    dp[i] = 1 + dp[j]
                    break
            ans = max(ans ,dp[i])
        return n - ans

从全局来看，所有区间中 \(\texttt{end}\) 最小的区间，可以作为最长的不重叠区间的第一个区间。

假设最长的区间为 \([a_1,b_1],[a_2,b_2],\cdots\)，如果存在 \([\texttt{start}_i,\texttt{end}_i]\) 且 \(a_1\lt\texttt{end}_i\le b_1\)（如果 \(\texttt{end}_i\le a_1\)，那么最长的区间就可以加上这个区间了），那么显然 \([\texttt{start}_i,\texttt{end}_i]\) 也可以作为第一个元素，因为 \(a_2\ge b_1\)，所以 \(a_2\ge\texttt{end}_i\)。

一旦确定了第一个区间，下一个区间同样是选择 \(\texttt{start}_j\ge a_1\) 且 \(\texttt{end}\) 最小的元素，这样就贪心的确定了最长的不重叠区间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        cnt = 0
        prev_end = -float("inf")
        for start, end in intervals:
            if start >= prev_end:
                cnt += 1
                prev_end = end
        return len(intervals) - cnt

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import heapq

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        q = [[y, x] for x, y in intervals]
        heapq.heapify(q)
        cnt = 0
        prev_end = -float("inf")
        while q:
            end, start = heapq.heappop(q)
            if start >= prev_end:
                cnt += 1
                prev_end = end
        return len(intervals) - cnt
返回顶部

在手机上阅读