一、题目
1、算法题目
“给定一个数组表示若干个区间的集合，请你合并所有重叠的区间，返回一个不重叠的区间数组，该数组需恰好覆盖输入的所有区间。”
题目链接：
来源：力扣（LeetCode）
链接：56. 合并区间 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
以数组 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、思路分析
这个题的关键在于对于二维数组排序的应用，比如说按照区间的最左边开始，在排完序的数组中，合并的区间是连续的。
首先将列表中的区间按照左端点升序排序，然后将第一个区间加入到苏中，然后按顺序加入剩余的区间。
再加入剩余的区间的时候，要考虑，如果当前区间的左端点在数组中最后一个区间的右端点之后，那么他们不会重合，可以将这个区间加入数组的末尾。
否则，就是重合了，将当前区间的右端点更新数组中最后一个区间的右端点，重置两者的较大值。
2、代码实现
代码参考：
public class Solution { public int[][] Merge(int[][] intervals) { //排序数组 Array.Sort(intervals, (x, y) => x[0].CompareTo(y[0])); //初始化变量 List<int[]> ans = new List<int[]>(); bool add; ans.Add(intervals[0]); //添加元素 for (int i = 1; i < intervals.Length; i++) { add = true; //遍历已有区间 foreach (int[] item in ans) { if (intervals[i][0]>item[1]||intervals[i][1]<item[0]) { continue; } item[0] = Math.Min(item[0], intervals[i][0]); item[1] = Math.Max(item[1], intervals[i][1]); add = false; } if (add) ans.Add(intervals[i]); } return ans.ToArray(); } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n log n)
其中n是数组的长度，只需要遍历一遍数组即可求得答案。
空间复杂度： O(log n)
只需要常数级别的空间存放变量。
三、总结
这道题要关键在于数组的排序，数组的排序需要找到左节点和右节点，最终形成一个数组。
所以，要遍历所有的数组，找到最小的值放到最左边，最大的值放到最右边。
最终得到想要的答案。
