25. Merge and Sort Intervals
Origin: Merge and Sort Intervals
Given an array of intervals [startTime, endTime], merge all overlapping intervals and return a sorted array of non-overlapping intervals.
Example
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation:
- 排序后初始化 merged 为
[1,3] [2,6]与[1,3]重叠（2 ≤ 3）→ 合并为[1,6][8,10]与[1,6]不重叠（8 > 6）→ 直接 append[15,18]与[8,10]不重叠 → 直接 append
Input Format
- 第一行：区间数量 N
- 第二行：单个区间数组长度（固定为 2）
- 接下来 N 行：每行两个空格分隔的整数 startTime endTime
- 区间可能任意顺序，可能有重复和完全包含的区间
Constraints
- 0 <= intervals.length <= 100000
- intervals[i].length == 2
- 0 <= intervals[i][0] < intervals[i][1] <= 10
Output Format
返回合并后的无重叠区间数组。
函数契约
// 输入：intervals（区间数组，每个元素 [start, end]）
// 输出：合并后的无重叠区间数组
// 边界：空数组 → []；单区间 → 原样返回；全部重叠 → 一个大区间
边界表
| 场景 | 返回什么 |
|---|---|
| 空数组 | [] |
| 单区间 | 原样返回 |
| 全部重叠 | 一个大区间 |
| 全部不重叠 | 排序后原样返回 |
| 包含关系 | 取较大的 end |
Resolution
我的解法
function mergeHighDefinitionIntervals(intervals: number[][]): number[][] {
if (!intervals?.length) return [];
const sorted = intervals.sort((a, b) => a[0] - b[0]);
const merged: number[][] = [];
merged.push(sorted[0]);
for (let i = 1; i < sorted.length; i++) {
const lastMerged = merged[merged.length - 1];
const current = sorted[i];
if (current[0] <= lastMerged[1]) {
lastMerged[1] = Math.max(lastMerged[1], current[1]);
} else {
merged.push(current);
}
}
return merged;
}解题思路
这道题本质是贪心：每次只看当前区间和最后一个已合并区间的关系，能合就合，不能合就追加。不回头、不反悔。
为什么是贪心？ 排序后区间按 start 从小到大排列，当前区间只可能和结果数组的最后一个区间重叠（因为后面的 start 更大）。不需要回头看前面的区间，贪心地处理当前这一个就够了。
为什么排序是关键？ 排序保证了：如果当前区间和最后一个不重叠，那它和前面所有已合并的都不重叠。不排序就无法保证这一点，需要两两比较。
贪心策略：
- 能合并就合并（
current[0] <= lastMerged[1]→ 取较大的 end） - 不能合并就追加（
current[0] > lastMerged[1]→ push）
和第 7 题（最大不重叠区间）对比：
- 第 7 题：贪心选最多不重叠区间，按 end 排序，每次选最早结束的
- 第 25 题：贪心合并重叠区间，按 start 排序，能合就合
同样是贪心，排序的依据不同（end vs start），因为目标不同（选最多 vs 合并所有）。
复杂度
- 时间：O(n log n)，排序是主要开销
- 空间：O(n)，最坏情况所有区间都不重叠，结果数组等于原数组
参考来源
- 相关文章：算法解题流程：从读题到提交的七步
- 相关题目：7. Maximum Number of Non-Overlapping Intervals — 同样是区间题，第 7 题是求最大不重叠数量，第 25 题是合并重叠区间