Non-overlapping Intervals
区间 i 从 starts[i] 延伸到 ends[i]。返回你必须移除的最少区间数，使剩下的区间两两不重叠。两个区间如果只是相接，也就是一个区间结束的时刻恰好是另一个区间开始的时刻，则它们不重叠。
函数
- startsinteger-array
- 每个区间的起点
- endsinteger-array
- 每个区间的末尾，索引与其起点相同
- 返回值integer
- 需要移除的最少区间数，使剩余区间互不重叠
约束条件
1 ≤ starts.length == ends.length ≤ 5000-5 × 104 ≤ starts[i] < ends[i] ≤ 5 × 104- 这些区间未排序。两个区间可能完全相同。
示例
- 输入
- starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
- 输出
- 2
- 解释
- 按开始时间排序，区间依次为 [1,4]、[2,3]、[3,6] 和 [5,7]。保留仅相接的 [2,3] 和 [3,6]，移除另外 2 个区间。不能保留 3 个区间：[1,4] 与 [2,3] 重叠，[3,6] 与 [5,7] 重叠。
- 输入
- starts = [0, 0, 0]ends = [5, 5, 5]
- 输出
- 2
- 解释
- 这三个区间都是 [0,5]，所以任意两个都重叠。保留一个，移除
2。
- 输入
- starts = [4, 1, 2]ends = [6, 2, 4]
- 输出
- 0
- 解释
- [1,2]、[2,4] 和 [4,6] 首尾相接，且从不重叠，所以你不需要移除任何内容，答案是
0。
进阶
假设每个区间都有一个值，而你想在互不重叠的区间中选出总值最大的组合。保留结束最早的区间仍然有效吗？
提示
逐个打开提示，每个都会多透露一点。
不要去想要移除什么，而要想要保留什么。你能保留的最大区间集合与答案有什么关系？
在所有区间中，最先结束的区间能为其余区间留出最多空间。某个最优答案总会保留它。
按结束位置对区间排序，然后遍历区间，并记住上一个保留区间的结束位置。起始位置大于或等于该结束位置的区间会被保留；其他区间都算作移除。
题解
移除数量最少的区间，就等于保留数量最多且互不重叠的区间：答案是 n 减去保留区间的数量。一个贪心规则可以在 O(n log n) 时间内找到这个数量：在仍然适合的区间中，始终保留结束最早的那个。
保留或移除每个区间
结果正确，但无法在最大的测试中运行完毕
思路
按起点对区间排序，并决定对每个区间保留还是移除。只有当某个区间的起点大于或等于上一个保留区间的终点时，才能保留它，这样保留的区间就会形成一条没有重叠的链。对每个区间都尝试两种选择，并取数量较大的结果；答案是 n 减去这个数量。
每个区间都可能让分支数量翻倍，因此 n 个区间最多会产生 2^n 条路径。30 个互不重叠的区间就意味着调用次数超过 10 亿次，而 n 最大可达 5000。
算法
- 按起点对区间排序，并让每个起点与它自己的终点保持对应。
- 定义
mostKept(i, last)：当last是最近保留的区间（没有区间时为-1）时，从位置i开始最多能保留的区间数。 - 如果已经超过末尾，则返回
0。否则，先取mostKept(i+1, last)，也就是移除区间i。 - 如果区间
i的起点大于或等于last的终点，也尝试1 + mostKept(i+1, i)，并保留较大的结果。 - 返回
n减去mostKept(0, -1)。
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
def most_kept(i, last):
# The most intervals you can keep among i..n-1, when interval last
# is the latest one kept so far (-1: nothing kept yet).
if i == n:
return 0
best = most_kept(i + 1, last) # remove interval i
if last == -1 or intervals[i][0] >= intervals[last][1]:
best = max(best, 1 + most_kept(i + 1, i)) # keep interval i
return best
return n - most_kept(0, -1)使用动态规划求最长链
结果正确，但无法在最大的测试中运行完毕
思路
搜索过程会反复问同一个问题：以这个区间结尾的最长链有多长？对每个区间回答一次。按起点排序，并令 chain[i] 表示以区间 i 为最后一个区间时最多能保留多少个区间。
可以紧接在 i 之前的区间，其结束时间不晚于 starts[i]，所以它的起点更早，在排序后的顺序中也更靠前。因此，对于最合适的 j，有 chain[i] = 1 + chain[j]；如果没有符合条件的区间，则为 1。在第一个示例中，这些值是 1、1、2 和 2，因此保留 2 个并删除 2 个。
双重循环会进行 n(n-1)/2 次检查：当 n = 5000 时，约为 1250 万次。
算法
- 按起点对区间排序，同时保留每个起点对应的终点。
- 为每个区间设置
chain[i] = 1。 - 对于每个
i，以及每个满足j < i且ends[j] ≤ starts[i]的j，如果chain[j]+1更大，就将chain[i]设置为chain[j]+1。 - 返回
n减去chain中的最大值。
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
# chain[i]: the most intervals you can keep when interval i is the last one kept
chain = [1] * n
for i in range(n):
for j in range(i):
if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
chain[i] = chain[j] + 1
return n - max(chain)贪心：保留结束时间最早的区间
思路
选择结束位置最小的区间。某个最优解会保留它：在任意一个能保留最多区间的集合中，用这个区间替换最早的那个区间。它的结束位置不会更晚，因此仍会在下一个保留区间开始前或开始时结束，集合大小不变，也不会出现重叠。所有开始位置早于它的结束位置的区间都会与它重叠，必须移除。剩下的问题就是处理开始位置不早于它的结束位置的区间。
在第一个示例中，按结束位置排序后，保留 [2,3]，移除 [1,4]，保留 [3,6]，移除 [5,7]。如果改为保留最短的区间，就会在 [1,5]、[4,7]、[6,10] 这个例子中失败：[4,7] 与另外两个区间都重叠，移除两个区间，而不是只移除一个。
排序的时间复杂度是 O(n log n)，遍历的时间复杂度是 O(n)。
算法
- 按结束位置对区间排序，并让每个结束位置与其对应的起始位置保持在一起。
- 保留第一个区间：将
lastEnd设为它的结束位置，并将removed设为0。 - 对于后续每个区间，如果它的起始位置大于或等于
lastEnd，就保留它，并将lastEnd设为它的结束位置。 - 否则，将
removed加 1。 - 返回
removed。
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(ends, starts)) # by end time
removed = 0
last_end = intervals[0][0] # the interval that ends first is always kept
for end, start in intervals[1:]:
if start >= last_end:
last_end = end # it fits after the last kept interval: keep it
else:
removed += 1 # it overlaps the last kept interval: remove it
return removed
易错点和边界情况
- 把首尾相接的区间视为重叠区间。如果使用
start > lastEnd而不是start ≥ lastEnd，区间链 [1,2]、[2,4]、[4,6] 会得到 1，而不是 0。 - 按起点排序，并在区间重叠时保留较早的区间。一个较宽的 [0,100] 随后会挤掉 [1,2]、[3,4] 和 [5,6]：需要移除 3 个区间，而不是 1 个。
- 将每个区间与排序列表中的相邻区间比较，而不是与最后保留的区间比较。在第一个示例中，[3,6] 必须与 [2,3] 的结束位置比较，而不是与已移除的 [1,4] 的结束位置比较，否则答案会是 3。
- 将
starts和ends分别作为两个列表排序。每个结束位置都必须与对应的起点保持在一起。 - 返回保留的区间数量，而不是移除的区间数量。
常见问题3
无重叠区间的时间复杂度是多少？
贪心解法按结束位置排序，复杂度为 O(n log n)，然后遍历一次所有区间，因此总复杂度为 O(n log n)，排序副本需要 O(n) 的空间。动态规划版本的复杂度为 O(n²)，而尝试保留每一种集合的复杂度为 O(2^n)。
可以改为按开始时间排序吗？
是的，只是重叠时采用不同的规则。按起点遍历这些区间；如果下一个区间与最后一个保留的区间重叠，就计为删除一个区间，并保留结束更早的那个。这样得到的删除数量相同，时间复杂度也是 O(n log n)。
“不重叠区间”和活动选择问题是一样的吗？
这是问题的另一面。活动选择问题要求找出最多的不重叠时间段；这个问题要求移除最少的时间段，也就是 n 减去前者的数量。使用相同的贪心规则，保留最先结束的活动，就能解决这两个问题。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def eraseOverlapIntervals(starts, ends):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
starts = [3, 1, 5, 2] ends = [6, 4, 7, 3]
预期输出
2