以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
https://leetcode-cn.com/problems/merge-intervals/
示例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
Java解法
思路：
- 依次遍历，判断其他区间与当前区间是否存在重叠，若存在进行合并跳出，再进行遍历
- 若不存在加入输出数组中
- 用到递归，所以空间占用并不是很高效
package sj.shimmer.algorithm.m2;
import java.util.ArrayList;
import java.util.List;
/**
* Created by SJ on 2021/2/27.
*/
class D34 {
public static void main(String[] args) {
int[][] merge = merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
int[][] merge1 = merge(new int[][]{{1, 4}, {4, 5}});
int[][] merge2 = merge(new int[][]{{2,3},{2,2},{3,3},{1,3},{5,7},{2,2},{4,6}});
for (int[] ints : merge2) {
for (int anInt : ints) {
System.out.print(anInt);
System.out.print(",");
}
System.out.println("---");
}
}
public static int[][] merge(int[][] intervals) {
List<int[]> list = new ArrayList<>();
for (int[] interval : intervals) {
list.add(interval);
}
List<int[]> merge = merge(list, 0);
return merge.toArray(new int[merge.size()][2]);
}
public static List<int[]> merge(List<int[]> lists,int index) {
if (lists != null&&lists.size()>index) {
int[] compare = lists.get(index);
for (int i = index+1; i < lists.size(); i++) {
int[] interval = lists.get(i);
//无重叠情况
if (interval[0]>compare[1]||interval[1]<compare[0]) {
if (i==lists.size()-1) {
return merge(lists,++index);
}
continue;
}else {
compare[0]=Math.min(interval[0],compare[0]);
compare[1]=Math.max(interval[1],compare[1]);
lists.remove(interval);
return merge(lists,index);
}
}
}
return lists;
}
}
image
官方解
https://leetcode-cn.com/problems/merge-intervals/solution/he-bing-qu-jian-by-leetcode-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()][]); }image
时间复杂度：O(n log n)
空间复杂度：O(log n)
