56. 合并区间(中等)

Blind 75 › 56. 合并区间(中等) (第 2 章)
文章工具

题目

给你一个区间数组 intervals,每个区间形如 [start, end],表示从 start 到 end 的连续一段。把所有有交集的区间合并成一个大区间,返回合并后的数组,要求合并后两两不重叠,并且整体恰好覆盖输入里的全部位置。

两个区间只要至少共享一个点,就算重叠——即使只共享端点。例如 [2,5] 和 [5,9] 重叠,应合并成 [2,9]。

自造示例一:输入 [[1,3],[2,4],[5,7],[6,8]],输出 [[1,4],[5,8]]。因为 [1,3] 与 [2,4] 合并成 [1,4],[5,7] 与 [6,8] 合并成 [5,8]。

自造示例二:输入 [[3,7],[1,4]],输出 [[1,7]]。注意输入顺序是乱的,但两个区间有交集,最终仍合并成一个。

约束:区间个数 1 ~ 104;每个区间长度固定为 2;0 ≤ start ≤ end ≤ 104。输入不保证有序。

思路

一句话:先按左端点排序,让“可能重叠”的区间排在一起;之后只比较相邻区间,线性扫描一次即可合并。

先想最直白的做法:拿每个区间和其余所有区间比较,有交集就合,合并之后继续和后面的比。这样一层套一层,最坏会反复扫描很多轮,接近 O(n²) 甚至更差,而且容易漏掉“合并后又能和更早的区间重叠”的情况。

关键观察有两点:

  • 两个区间重叠的充要条件是 a.start ≤ b.end 且 b.start ≤ a.end。
  • 一旦按左端点升序排好,若当前区间的右端点小于下一个区间的左端点,那么它与后面所有区间都不可能再重叠——因为后面的左端点只会更大。

于是“谁和谁可能重叠”从一张两两比较的大网,退化成“相邻区间之间”的比较:维护最后一个还没关闭的合并区间,遇到能接上的就扩展它的右端点,遇到接不上的就把它定稿、另起一个新区间。

🔒

本篇为付费内容

您已阅读试读部分,购买后即可解锁全文。

⚠️ 本站内容已做唯一性标记并受版权保护,未经授权禁止转载,侵权必究。

还没有评论,来说两句?

发表评论

欢迎交流技术细节;广告与人身攻击会被删除。

在线咨询