十四 56. 合并区间

56. 合并区间https://leetcode.cn/problems/merge-intervals/

以数组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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

class Solution { public int[][] merge(int[][] intervals) { // 特殊情况处理 if(intervals == null || intervals.length <= 1){ return intervals; } // 1. 按区间开始位置排序（如果开始相同，按结束排） Arrays.sort(intervals, (a, b) -> { if(a != b){ return a[0] - b[0];// 按开始位置升序 } return a[1] - b[1];// 开始相同，按结束位置升序 }); // 2. 使用List存储结果（不知道最终有几个区间） List<int[]> result = new ArrayList<>(); // 3. 初始化当前区间为第一个 int curStart = intervals[0][0]; int curEnd = intervals[0][1]; // 4. 从第二个开始遍历 for(int i = 1; i < intervals.length; i++){ int start = intervals[i][0]; int end = intervals[i][1]; if(curEnd >= start){ // 重叠：扩展当前区间 curEnd = Math.max(curEnd, end); // 取较大的结束位置 }else{ // 不重叠：保存当前区间，开启新区间 result.add(new int[]{curStart, curEnd}); curStart = start; curEnd = end; } } // 5. 别忘了最后一个区间！ result.add(new int[]{curStart, curEnd}); // 6. List转数组返回 return result.toArray(new int[result.size()][]); } }

Lambda 表达式语法拆解

Arrays.sort(intervals, (a, b) -> { ... }); // ↑ ↑ // 待排序数组 Lambda表达式

2.1 为什么能这么写？

Arrays.sort()有两个重载版本：

// 版本1：只传数组，按自然顺序排（基本类型升序） public static void sort(int[] a) // 版本2：传数组 + 比较器，自定义排序规则 public static <T> void sort(T[] a, Comparator<? super T> c) // ↑ // 这里需要 Comparator 对象

Comparator是一个函数式接口（只有一个抽象方法）：

@FunctionalInterface public interface Comparator<T> { int compare(T o1, T o2); // 只有一个抽象方法 // ... 其他是 default/static 方法 }

Lambda 的本质：因为Comparator只有一个抽象方法，编译器能自动推断(a, b) -> {...}就是在实现compare方法。

逐行解释代码逻辑

Arrays.sort(intervals, (a, b) -> { // a, b 代表两个要比较的区间（int[]类型） // 第一关键字：按区间开始位置排序 if (a[0] != b[0]) { return a[0] - b[0]; // 升序：小的在前 } // 第二关键字：开始位置相同，按结束位置排序 return a[1] - b[1]; // 升序：小的在前 });