56. 合并区间
题目描述
输入区间数组 intervals，每一项 intervals[i] = [starti, endi] 表示一个闭区间。
只要两个区间有公共点（端点相接也算），就把它们合并成一个。反复合并，直到没有任何两个区间重叠。
返回合并后的区间数组。结果中的区间互不重叠，且覆盖的范围与输入完全相同。区间的先后顺序不限。
示例 1
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]]
解释：[1,3] 与 [2,6] 有交集，合成 [1,6]，其余区间保持不变。
示例 2
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]]
解释：[1,4] 与 [4,5] 在 4 处相接，算作重叠，合成 [1,5]。
示例 3
输入：intervals = [[4,7],[1,4]] 输出：[[1,7]]
解释：输入未必有序；[1,4] 与 [4,7] 相接，合成 [1,7]。
数据范围
1 <= intervals.length <= 10^4intervals[i].length == 20 <= starti <= endi <= 10^4
解题思路
按起点排序，维护结果最后一个区间。若新区间起点不超过当前终点就扩展终点，否则开启新区间。
为什么正确
结果已按起点排序且互不重叠；最后一个区间覆盖已处理部分中能与它相连的范围。
复杂度分析
时间 O(n log n)，空间 O(n)。
易错点
不排序就比较相邻区间，可能错过跨越多个区间的重叠。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def merge(self, intervals):
intervals.sort()
ans=[]
for start,end in intervals:
if not ans or start>ans[-1][1]: ans.append([start,end])
else: ans[-1][1]=max(ans[-1][1],end)
return ansclass Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
List<int[]> ans = new ArrayList<>();
for (int[] it : intervals) {
int start = it[0], end = it[1];
if (ans.isEmpty() || start > ans.get(ans.size() - 1)[1]) ans.add(new int[]{start, end});
else ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], end);
}
return ans.toArray(new int[0][]);
}
}class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
for (auto& it : intervals) {
int start = it[0], end = it[1];
if (ans.empty() || start > ans.back()[1]) ans.push_back({start, end});
else ans.back()[1] = max(ans.back()[1], end);
}
return ans;
}
};func merge(intervals [][]int) [][]int {
sort.Slice(intervals, func(a, b int) bool {
if intervals[a][0] != intervals[b][0] {
return intervals[a][0] < intervals[b][0]
}
return intervals[a][1] < intervals[b][1]
})
ans := [][]int{}
for _, it := range intervals {
start, end := it[0], it[1]
if len(ans) == 0 || start > ans[len(ans)-1][1] {
ans = append(ans, []int{start, end})
} else {
ans[len(ans)-1][1] = max(ans[len(ans)-1][1], end)
}
}
return ans
}var merge = function(intervals) {
intervals.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const ans = [];
for (const [start, end] of intervals) {
if (!ans.length || start > ans[ans.length - 1][1]) ans.push([start, end]);
else ans[ans.length - 1][1] = Math.max(ans[ans.length - 1][1], end);
}
return ans;
};function merge(intervals: number[][]): number[][] {
intervals.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const ans: number[][] = [];
for (const [start, end] of intervals) {
if (!ans.length || start > ans[ans.length - 1][1]) ans.push([start, end]);
else ans[ans.length - 1][1] = Math.max(ans[ans.length - 1][1], end);
}
return ans;
};