京公网安备11010502063487号给一堆区间,比如 [1,4] [2,3] [6,7],把有重叠的合并到一起,得到 [1,4] [6,7]——[2,3] 整个被 [1,4] 包住了。思路是先按起点排序,再扫一遍:能接上就合并,接不上就另起一段。这跟之前高峰在线人数系列是同一个"先排序、再扫一遍"的套路。
暴力法思路很直接:开一个覆盖标记数组,每个区间覆盖到的位置都标记为 true,最后找连续为 true 的段——这就是合并结果。拿你的例子和几个无歧义的边界情况(嵌套、部分重叠、共享端点)交叉验证:
merge_greedy([[1,4],[2,3],[6,7]]) # 嵌套区间(你给的例子) merge_greedy([[1,3],[2,6],[8,10],[15,18]]) # 部分重叠 merge_greedy([[1,4],[4,5]]) # 共享端点[[1,4],[2,3],[6,7]] -> 贪心=[(1,4),(6,7)] 暴力=[(1,4),(6,7)] 一致=True [[1,3],[2,6],[8,10],[15,18]] -> 贪心=[(1,6),(8,10),(15,18)] 暴力=[(1,6),(8,10),(15,18)] 一致=True [[1,4],[4,5]] -> 贪心=[(1,5)] 暴力=[(1,5)] 一致=True
三种情况——完全被包住、部分重叠、只共享一个端点——贪心排序法和暴力标记法结果完全一致。关键判断只有一句:排序后,只要当前区间的起点 start <= 上一段的终点,就说明接上了,用 max(上一段终点, 当前终点) 更新——这一步同时处理了"部分重叠"和"完全包住"两种情况,不用分开写。
试着验证 [1,4] 和 [5,6] 该不该合并时,真实踩了一个坑:暴力法用整数数组标记覆盖位置,而整数数组里 4 和 5 是相邻下标,中间没有任何空位——这意味着暴力法天然就会把它们判定成"连续、该合并",不管你的区间本意是不是"连续实数意义上的两段各自独立的范围"。换句话说,一旦把区间摊开成整数数组,"两个区间之间到底有没有空隙"这个信息就已经丢了。
merge_greedy([[1,4],[5,6]], adjacent_touch=False) # 经典定义:只有真正共享点才合并 merge_brute([[1,4],[5,6]], lo=1, hi=6) # 暴力法(整数覆盖数组)贪心(经典定义): [(1, 4), (5, 6)] <- 不合并 暴力(整数数组): [(1, 6)] <- 合并了!两者不一致
这不是贪心算法错了,是这次暴力验证方法本身选错了工具——用整数数组做覆盖标记,天然只能验证"整数区间语义下,首尾相邻算不算重叠"这一种约定,没法验证"两个区间是不是共享至少一个点"这种更严格的经典定义。真正该用哪种约定,取决于业务场景:
# 经典定义(LeetCode "合并区间"用的就是这个):只有真正共享点才合并 merge_greedy([[1,4],[5,6]], adjacent_touch=False) -> [(1, 4), (5, 6)] # 不合并 # 整数相邻定义(比如排班表:第1~4天请假,第5~6天又请假,算连续6天请假) merge_greedy([[1,4],[5,6]], adjacent_touch=True) -> [(1, 6)] # 合并
两种写法只差一个 +1(判断条件从 start <= last_end 变成 start <= last_end + 1),但语义完全不同。写代码之前必须先跟需求方确认清楚是哪种场景,不能凭直觉选一个就开始写。
跟高峰在线人数系列的思路完全一样:每个区间是一次"区间内 +1"的操作,用差分数组记录,最后扫一遍找"覆盖次数 > 0"的连续段,就是合并结果。前提和之前一样——只有值域范围不大的时候才划算:
N = 200_000 # 区间数量 值域 = [0, 100_000] merge_greedy(intervals) # 排序贪心版 merge_diff_array(intervals, 0, 100_000) # 差分数组版结果完全一致: True 贪心排序版耗时: 74.5 ms 差分数组版耗时: 13.1 ms
差分数组版快了约 5.7 倍,因为它不需要排序,只是"标记 + 扫一遍"。但如果区间的坐标是真实时间戳(值域动辄几十亿)或者浮点数,差分数组这条路直接走不通(数组开不出这么大,浮点数也没法当数组下标)——这时候只能用排序贪心版,这也是为什么排序贪心版才是更通用的解法,差分数组只是"值域小"这个特定条件下的优化。
6 个区间(原始顺序):[6,7] [1,4] [2,3] [9,12] [11,13] [15,15]。点击"下一步"看排序后如何逐个扫描合并。