当前位置：首页 > news >正文

力扣第五十六题——合并区间

news 来源：原创 2024/9/20 3:03:10

内容介绍

以数组 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

完整代码

 class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0) {return new int[0][2];}Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});List<int[]> merged = new ArrayList<int[]>();for (int i = 0; i < intervals.length; ++i) {int L = intervals[i][0], R = intervals[i][1];if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {merged.add(new int[]{L, R});} else {merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);}}return merged.toArray(new int[merged.size()][]);}
}

思路详解

一、问题背景

给定一个二维数组intervals，其中每个子数组表示一个区间，我们需要合并这些区间，使得没有重叠的区间尽可能紧密相连。

二、解题思路

排序：
- 首先，我们需要对intervals数组进行排序。排序的依据是每个子数组的开头位置，因为合并的目的是让没有重叠的区间尽可能紧密相连。
合并区间：
- 创建一个List<int[]>，用于存储合并后的区间。
- 遍历排序后的intervals数组，对于每个区间，如果当前列表为空或者当前区间的左端点大于列表中最后一个区间的右端点，则将当前区间添加到列表中。
- 如果当前区间的左端点小于或等于列表中最后一个区间的右端点，则将列表中最后一个区间的右端点更新为当前区间右端点中的较大者。
返回结果：
- 遍历完成后，将List<int[]>转换为二维数组并返回。

三、代码详解

排序：
- 使用Arrays.sort方法对intervals数组进行排序，比较器比较的是每个子数组的第一个元素。

Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}
});

合并区间：
- 创建一个List<int[]>，用于存储合并后的区间。
- 遍历排序后的intervals数组，对于每个区间，根据合并策略添加或更新列表中的区间。

List<int[]> merged = new ArrayList<int[]>();
for (int i = 0; i < intervals.length; ++i) {int L = intervals[i][0], R = intervals[i][1];if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {merged.add(new int[]{L, R});} else {merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);}
}

返回结果：
- 遍历完成后，将List<int[]>转换为二维数组并返回。

return merged.toArray(new int[merged.size()][]);

四、总结

通过上述步骤，我们能够有效地合并区间，使得没有重叠的区间尽可能紧密相连。关键在于正确地排序区间并合并它们。这种方法的时间复杂度为O(n log n)，其中n是intervals数组的长度，因为排序操作的时间复杂度为O(n log n)。空间复杂度为O(n)，用于存储合并后的区间。

知识点精炼

一、核心概念

排序算法：在解决组合问题时，排序可以帮助我们找到最优解或近似解。
动态规划：在某些情况下，我们可以通过动态规划来优化算法，减少重复计算。
二维数组：在处理与位置相关的数据时，二维数组是一个非常有用的数据结构。

二、知识点精炼

区间合并问题：
- 给定一个二维数组intervals，其中每个子数组表示一个区间，需要合并这些区间，使得没有重叠的区间尽可能紧密相连。
排序：
- 使用Arrays.sort方法对intervals数组进行排序，比较器比较的是每个子数组的第一个元素。
合并区间：
- 遍历排序后的intervals数组，对于每个区间，根据合并策略添加或更新列表中的区间。
返回结果：
- 遍历完成后，将List<int[]>转换为二维数组并返回。

三、性能分析

时间复杂度：O(n log n)，其中n是intervals数组的长度，因为排序操作的时间复杂度为O(n log n)。
空间复杂度：O(n)，用于存储合并后的区间。

四、实际应用

数据处理：在处理与位置相关的数据时，这种算法可以帮助我们合并区间，使得没有重叠的区间尽可能紧密相连。
算法竞赛：在算法竞赛中，掌握这种算法对于解决与区间合并相关的问题非常有帮助。

五、代码实现要点

排序：正确使用Arrays.sort方法进行排序。
合并区间：正确实现合并策略，避免数组越界和重复添加。
返回结果：正确返回合并后的区间数组。

合并时如何避免重复

排序：首先对所有区间进行排序，确保每个区间的起始位置是唯一的。
迭代合并：遍历排序后的区间列表，对于每个区间，检查它是否与列表中的最后一个区间重叠或完全包含在最后一个区间内。如果是，则更新最后一个区间的结束位置；如果不是，则将当前区间添加到列表中。
去重：在添加新区间之前，检查它是否已经在列表中。如果是，则跳过它，避免重复添加。
返回结果：遍历完成后，将合并后的区间列表转换为二维数组并返回。

以下是代码实现：

class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0) {return new int[0][2];}Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});List<int[]> merged = new ArrayList<>();int[] last = intervals[0];merged.add(last);for (int i = 1; i < intervals.length; i++) {int[] current = intervals[i];if (current[0] <= last[1]) {// 如果当前区间与最后一个区间重叠，更新最后一个区间的结束位置last[1] = Math.max(last[1], current[1]);} else {// 如果当前区间与最后一个区间不重叠，添加当前区间merged.add(current);last = current;}}return merged.toArray(new int[merged.size()][]);}
}

在这个实现中，我们首先对区间进行排序，然后遍历排序后的区间列表。对于每个区间，我们检查它是否与列表中的最后一个区间重叠或包含在最后一个区间内。如果是，我们更新最后一个区间的结束位置；如果不是，我们将当前区间添加到列表中。这样，我们就能够确保不会重复添加区间，也不会将已经包含在当前合并区间内的区间再次添加。