LeetCode Hot100刷题——合并区间

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] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

实现步骤

1. 检查输入数组是否为空或长度为0，如果是，直接返回空数组。
2. 否则，对intervals数组进行排序。使用Arrays.sort自定义Comparator。
3. 创建merged列表，初始时加入第一个区间。
4. 遍历从第二个区间开始的所有区间。
5. 获取merged列表的最后一个区间。
6. 比较当前区间的start和最后一个区间的end。
7. 如果当前区间的start <= 最后一个区间的end，则合并，更新最后一个区间的end为两者的最大值。
8. 否则，直接将当前区间加入merged列表。
9. 最后，将merged列表转换为数组返回。

程序代码

• 排序区间：首先将所有区间按照起始点进行排序。这样可以确保所有可能重叠的区间都是连续的。
• 合并重叠区间：遍历排序后的区间，逐个合并重叠的区间。具体来说，维护一个合并后的区间结果列表，如果当前区间与前一个合并后的区间重叠，则合并它们；否则，将当前区间添加到结果列表中。

class Solution {public int[][] merge(int[][] intervals) {// 数组为空（长度为0）if(intervals.length == 0){return new int[0][];}// 按区间的起始点进行排序Arrays.sort(intervals,(a,b) -> Integer.compare(a[0], b[0]));// 结果列表List<int[]> merged = new ArrayList<>();// 初始时加入第一个区间merged.add(intervals[0]);for(int i = 1; i < intervals.length; i++){int[] last = merged.get(merged.size() - 1);int[] current = intervals[i];// 当前区间的起始点小于等于上一个区间的结束点，说明有重叠if(current[0] <= last[1]){// 合并区间，更新结束点为两者较大的那个last[1] = Math.max(last[1],current[1]);} else{// 无重叠，直接添加当前区间merged.add(current);}}return merged.toArray(new int[merged.size()][]);}
}

补充：使用 Lambda 表达式对区间数组按起始点升序排序

在Java中，Arrays.sort()方法的第二个参数可以接收一个Comparator对象，用于定义排序规则。Lambda表达式在这里的作用是简化Comparator的匿名内部类的定义，直接描述两个区间如何比较大小。

Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

解析：

        Arrays.sort()的作用：对数组intervals进行排序，排序规则由第二个参数（Lambda表达式）决定。

        Lambda表达式 (a,b) -> ...：

                1. a 和 b 是待比较的两个区间（即intervals中的两个元素，类型是int[ ]）。

                2. a[0] 和 b[0] 分别表示这两个区间的起始点。

                3. Integer.compare(a[0]，b[0]）的作用是：比较两个起始点的大小。

        比较逻辑：

                如果 a[0] < b[0]，返回负数，表示a应该排在b的前面（升序）。

                如果 a[0] > b[0]，返回正数，表示a应该排在b的后面（降序）。

                如果相等，返回0，表示顺序不变。

Lambda表达式与传统写法的对比：

如果不使用Lambda表达式，代码需要定义一个匿名的Comparator：

Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] a, int[] b) {return Integer.compare(a[0], b[0]);}
});