# \[435]\[中等]\[贪心]\[动态规划] 无重叠区间

## 问题描述

[435. 无重叠区间](https://leetcode-cn.com/problems/non-overlapping-intervals/)

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

注意:

* 可以认为区间的终点总是大于它的起点。
* 区间 \[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

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

## 解题思路

换一个角度来看, 我们看移除掉重叠的区间, 剩下的元素, 后面区间的第一个元素, 一定不小于前面区间的后一个元素. 实际上还是一个**求最大递增子序列**的题目, 只是由严格递增变成了非严格递增, 而比较元素大小的方式变成了比较排序后, 后面区间的左端和前面区间右端的大小. 其余保持相同.

### 动态规划

```python
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        if n == 0:
            return 0
        intervals.sort()

        dp = [1] * n
        max_len = 1
        for j in range(n):
            for i in range(j):
                if intervals[j][0] >= intervals[i][1] and dp[i] >= dp[j]:
                    dp[j] = dp[i] + 1
                    max_len = max(max_len, dp[j])
        return n - max_len
```

### 贪心

类似于[\[300\]\[中等\]\[贪心\]\[二分\]\[动态规划\]\[树状数组\] 最长上升子序列](https://blessbingo.gitbook.io/garnet/suan-fa/shu-zu/broken-reference)中, 不断扩展最长子序列的长度. 但这里比较特殊, 不再是简单的数字之间的比较, 而是区间的比较, 但区间的大小无法定义.

我们知道递增的区间序列, 它的右端序列和左端序列肯定也是递增的. 可以对原数组的每个区间, 按区间的右端排序. 我们假设排序后, 对于位置`i`的区间`A`, 考虑`i + 1`位置的区间`B`, 如果`B`与`A`不重叠, 即`B`的左端不小于`A`的右端, 则它们可以组成递增序列; 但若两者重叠, 最长递增子序列在这一部分只能2选1, 且它与`A`区间可能的关系如下:

```
  【————】                i区间, 记为A
      【————】            i+1区间的一种可能, 记为B, 与区间A部分重叠
【————————————————】      i+1区间的另一种可能, 记为C, 完全涵盖A区间
```

对于`B`和`C`的情况, 能与`B`或`C`组成递增序列的后续区间, 也一定能与`A`组成递增序列, 但反过来不行. 而且`A`的右端最小, 留给后面的空间更大, 最终的递增序列一定是一系列区间右端最小的区间集合.

因此贪心算法, 我们在找下一个最长递增序列的区间时, 找到剩余的第一个与现有区间不重叠的(根据题目端点可以重叠)的区间, 这个区间一定是最终递增序列的一部分.

```python
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])

        length = []
        for left, right in intervals:
            if len(length) == 0 or left >= length[-1]:
                length.append(right)
        return n - len(length)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/shu-zu/435-wu-zhong-die-qu-jian.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.