题目来源于力扣题库,题目链接:LC56.合并区间
Q:以数组 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
A:思路:
以下是Java代码,仅供参考:
package algo;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
class mergeSolution_56{
public int[][] merge(int[][] intervals){
if(intervals.length == 1) return intervals; // 如果题目给出的二维数组长度为1,则不需要合并,直接返回intervals
Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0])); // 现将多个区间按照其左边界排序,这样可以简化问题
List<int[]> res = new LinkedList<>();
int start = intervals[0][0];
int end = intervals[0][1];
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0] > end){ // 不重合,说明该区间不需要与后面的区间进行比较了,即其为结果之一,加入结果集即可
res.add(new int[]{start, end}); // 加入当前的 [start, end] 区间
start = intervals[i][0]; // 更新start
end = intervals[i][1]; // 更新end
}else{
end = Math.max(end, intervals[i][1]); // 重合,更新右边界
}
}
res.add(new int[]{start, end});
return res.toArray(new int[res.size()][]);
}
/* 测试 */
public static void main(String[] args) {
mergeSolution_56 solution_56 = new mergeSolution_56();
int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
int[][] answer = solution_56.merge(intervals);
for (int[] is : answer) {
System.out.println(Arrays.toString(is));
}
}
}