合并区间

题目

以数组 intervals 表示若干个区间的集合&＃xff0c;其中单个区间为 intervals[i] &＃61; [starti, endi] 。请你合并所有重叠的区间&＃xff0c;并返回 一个不重叠的区间数组&＃xff0c;该数组需恰好覆盖输入中的所有区间 。

解析

本题思路相对比较容易想

1. 先对各个区间按左边界从小到大进行排序

2. 顺序对重叠区间进行聚合

1. 第一个作为基准

2. 从第二个开始&＃xff0c;比较区间左边界是否小于等于基准区间的有边界&＃xff0c;若符合&＃xff0c;则说明两个区间有重叠&＃xff0c;可以聚合&＃xff0c;也就是说两者的右边界&＃xff0c;哪个大选哪个作为基准区间的右边界。

3. 以此类推&＃xff0c;直到不符合条件&＃xff0c;则第一个聚合区间形成。并把当前区间作为基准区间再从第一步重新开始执行

但是这个题目在编码的时候会遇到几个基础的编码知识&＃xff0c;比较容易遗忘。

对二维数组进行排序

我们知道对一维数组int[] a进行排序的话&＃xff0c;可以使用Arrays.sort(a)完成。但是二维数组呢&＃xff1f;

二维数组可以用该函数的重载函数 sort(T[] a, Comparator c)&＃xff0c;通过指定要比较哪个字段&＃xff0c;就可以实现对二维数组的排序了。

list中装数组

List list &＃61; new ArrayList(); 大家见过吗&＃xff1f;不管见没见过&＃xff0c;这样的写法都是没问题的&＃xff0c;因为数组也是一个对象&＃xff0c;可以放在list中。

List转化为数组

List list 想转化为list&＃xff0c;就可以通过list.toArray()方法直接转化为二维数组。

代码实现

publicint[][] merge(int[][] intervals) {

if (intervals.length&＃61;&＃61;0) {

returnnewint[0][2];

}

if(intervals.length&＃61;&＃61;1) {

returnintervals;

}

//这里是对二维数组按左边界排序

Arrays.sort(intervals, newComparator() {

publicintcompare(int[] interval1, int[] interval2) {

returninterval1[0] -interval2[0];

}

});

​

//把数组装到list中

Listmerged&＃61;newArrayList();

intstart&＃61;intervals[0][0];

intend &＃61;intervals[0][1];

for (inti&＃61;0; i

while (&＃43;&＃43;i

if (intervals[i][0] >end) {

break;

}

end&＃61;Math.max(end, intervals[i][1]);

}

merged.add(newint[]{start, end});

if (i&＃61;&＃61;intervals.length) {

break;

}

start&＃61;intervals[i][0];

end&＃61;intervals[i][1];

}

//list转为二维数组

returnmerged.toArray(newint[merged.size()][]);

}