4.合并区间
LeeCode-56、合并区间
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
- 1 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= starti <= endi <= 10^4
思路:
1、对二维数组按照第一列升序排序
2、进行合并数组
- int term[] =intervals[0],作为临时空间,判断是否需要合并集合和是否放入结果集
- 若上一个数组的右边值>=下一个数组的左边值,则比较两个数组右边的值
- 若上一个数组的右边值<下一个数组的左边值,则将上一个数组放进列表中,下一个数组接力,如果是最后一个数组,则直接加进去即可
- 最后一个也要加入,否则会漏掉
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return intervals;
//1、对二维数组按照第一列升序排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
//2、进行合并数组
List<int []> list = new ArrayList<>();
int term[] =intervals[0]; //临时空间,1 判断是否需要合并集合,2 是否放入结果集
//term[0]=最左边的,term[1]:动态的右边,循环直到右边小于其它的左边任何数,才停止,并加入list
for (int i = 1; i < intervals.length; i++) {
if (term[1]>=intervals[i][0]){ //上一个数组的右边值>=下一个数组的左边值
term[1]=Math.max(term[1],intervals[i][1]); //比较两个数组右边的值
}else {
list.add(term); //将上一个数组放进列表中
term=intervals[i]; //下一个数组接力,如果是最后一个数组,则直接加进去即可
}
}
list.add(term); //最后一个
return list.toArray(new int[list.size()][2]);//列表转化成数组,并必须进行数据初始化
}
}