区间常见问题
一般区间题目是线段树来做。例如区间sum，max等
还有类普通区间的插入合并等，这个可以单纯的贪心(开始节点排序)等来做。
题型和模板
按开始位置排序
- 合并。 [l1,r1], [l2,r2] 的合并后区间为 [ min(l1,l2), max(r1,r2)]
- 区间插入，其实就是把可合并的合并到一起。左边右边都有可合并的。比如57. 插入区间 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠.
- 开始节点排序
- 区间插入，其实就是把可合并的合并到一起。左边右边都有可合并的。比如57. 插入区间 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠.
- 一次遍历，看是否有重叠。
按结束位置排序
- 贪心，求最多无重叠区间数量。 贪心理由: 第一个最早结束的必然是不重叠的选择结果。依次贪心。
- 求不重叠区间的最大数量 。 435. 无重叠区间 给定一个区间的集合
intervals，其中intervals[i] = [starti, endi]。返回 需要移除区间的最小数量，使剩余区间互不重叠 。- 按照右边节点排序，贪心。O(nlogn)。 可以直接套用模板。
- 带权的日程选择问题。 给定 n 个闭区间 [left_i,right_i,score_i]. 请你在数轴上选择若干区间,使得选中的区间之间互不相交. 返回可选取区间的最大权值和. 通用解法是 线性dp + 二分。参考
- 模板: 比如对2830. 销售利润最大化 来说.
- 求不重叠区间的最大数量 。 435. 无重叠区间 给定一个区间的集合
模板 求最多不相交区间
class Solution:
def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
d = collections.defaultdict(list)
for s, e, g in offers:
d[e].append((s, e, g))
from typing import List, Tuple
from bisect import bisect_left, bisect_right
def weightedIntervalScheduling(intervals: List[Tuple[int, int, int]], could_overlapping=False) -> int:
"""
给定 n 个闭区间 [left_i,right_i,score_i].
请你在数轴上选择若干区间,使得选中的区间之间互不相交.
返回可选取区间的最大权值和.
end点进行排序 + DP找最大. O(nlogn)
Args:
intervals: 区间列表,每个区间为[left,right,score].
could_overlapping: 是否允许选择的区间端点重合.默认为False.
"""
n = len(intervals)
intervals = sorted(intervals, key=lambda x: x[1])
pre = [0] * n
# 找第一个有重叠的区间的位置i, 从0开始
find_next = bisect_right if could_overlapping else bisect_left
for i in range(n):
start = intervals[i][0]
pre[i] = find_next(intervals, start, key=lambda x: x[1])
dp = [0] * (n + 1)
# dp[i] 表示前i个区间的最大值。从1开始
for i in range(n):
dp[i + 1] = max(dp[i], dp[pre[i]] + intervals[i][2])
return dp[n]
return weightedIntervalScheduling(offers)
设置score_i 为1，就是求不重叠区间的数目。
扫描线。 求区间重叠的最多数量，扫描线。遇到start则+1, end则-1. O(n)。
应用
354. 俄罗斯套娃信封问题 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
- 其实是个二维的找最长递增子序列，需要a1<a2, b1 < a2 对于[a,b]这样的长宽信封来说。 如果按a有序+ LIS o(nlogn)的模板，会错误的统计到a相同时的结果，所以可以按a有序+按b倒序，这样求b的LIS就是正确的了
57. 插入区间 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠
- 左边不相交直接append 有相交的会合并成一个 右边不相交直接append
class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: res = [] i = 0 # 左边不相交直接append while i < len(intervals) and intervals[i][1] < newInterval[0]: res.append(intervals[i]) i += 1 # 有相交的会合并成一个 while i < len(intervals) and intervals[i][0] <= newInterval[1]: newInterval[1] = max(newInterval[1], intervals[i][1]) newInterval[0] = min(newInterval[0], intervals[i][0]) i += 1 res.append(newInterval) # 右边不相交直接append while i < len(intervals): res.append(intervals[i]) i += 1 return res区间贪心 参考另一个blog
57. 插入区间 如上， 按start排序，遇到重叠就合并,start = min(start, left), right= max(right, end)
56.合并区间 以数组
intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。合并区间，按start排序
class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda x: x[0]) merged = [] for interval in intervals: # 如果列表为空，或者当前区间与上一区间不重合，直接添加 if not merged or merged[-1][1] < interval[0]: merged.append(interval) else: # 否则的话，我们就可以与上一区间进行合并 merged[-1][1] = max(merged[-1][1], interval[1]) return merged- 435. 无重叠区间 给定一个区间的集合
intervals，其中intervals[i] = [starti, endi]。返回 需要移除区间的最小数量，使剩余区间互不重叠 。 按照右边节点排序，贪心。O(nlogn) 选首区间策略
- 其实就是求不重叠区间的最大数量
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)
right = intervals[0][1]
ans = 1
for i in range(1, n):
if intervals[i][0] >= right:
ans += 1
right = intervals[i][1]
return n - ans
套用模板后
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals = [(x[0], x[1], 1) for x in intervals]
return len(intervals) - weightedIntervalScheduling(items, True)
- Meeting Rooms (Leetcode Premium) Given an array of meeting time intervals consisting of start and end times
[[s1,e1],[s2,e2],...](si< ei), determine if a person could attend all meetings.
解答: 按start排序，看有无重合区间
- Meeting Rooms II (Leetcode Premium) Given an array of meeting time intervals consisting of start and end times
[[s1,e1],[s2,e2],...](si< ei), find the minimum number of conference rooms required.
可以用heap弹出，复杂度高。最佳是扫描线算法。遇到start则+1, end则-1.
是**求区间重叠的最多数量，扫描线。**