贪心与堆中等1 种解法
#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] 可被视为重叠区间。
示例 3：
输入：intervals = [[4,7],[1,4]] 输出：[[1,7]] 解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
解题主线
- 按左端点排序后，只需比较当前区间左端点与已合并末区间右端点。
解法 1：排序后线性合并
按起点升序扫描；不重叠则新增区间，重叠则扩展最后区间的右端点。
-
时间复杂度： O(n log n)
-
空间复杂度： O(n)，用于结果；排序额外栈空间取决于实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
final class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[0][2];
Arrays.sort(intervals, (first, second) -> Integer.compare(first[0], second[0]));
List<int[]> merged = new ArrayList<>();
// 排序后，当前待合并区间 [left, right] 覆盖所有尚未写入结果的重叠区间。
int left = intervals[0][0];
int right = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
// 新区间起点越过 right 才能确认当前区间已无法继续扩展。
if (intervals[i][0] > right) {
merged.add(new int[] {left, right});
left = intervals[i][0];
right = intervals[i][1];
} else {
right = Math.max(right, intervals[i][1]);
}
}
merged.add(new int[] {left, right});
return merged.toArray(int[][]::new);
}
}实现提示
- 合并旧代码中仅 LinkedList/ArrayList 写法不同的重复实现，并补空输入保护。
边界与易错点
- 被包含区间不能缩小右边界，合并时必须取 max。
- 比较器使用减法可能溢出，应使用 Integer.compare。
- 旧文件两个方法只是结果容器不同，按同一贪心解法合并。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q056_mergeIntervals.java