12306网站建设 实际今日头条荆州新闻
合并区间
题目
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
解析
本题思路相对比较容易想
先对各个区间按左边界从小到大进行排序
顺序对重叠区间进行聚合
第一个作为基准
从第二个开始，比较区间左边界是否小于等于基准区间的有边界，若符合，则说明两个区间有重叠，可以聚合，也就是说两者的右边界，哪个大选哪个作为基准区间的右边界。
以此类推，直到不符合条件，则第一个聚合区间形成。并把当前区间作为基准区间再从第一步重新开始执行
但是这个题目在编码的时候会遇到几个基础的编码知识，比较容易遗忘。
对二维数组进行排序
我们知道对一维数组int[] a进行排序的话，可以使用Arrays.sort(a)完成。但是二维数组呢？
二维数组可以用该函数的重载函数 sort(T[] a, Comparator<? super T> c)，通过指定要比较哪个字段，就可以实现对二维数组的排序了。
list中装数组
List<int[]> list = new ArrayList(); 大家见过吗？不管见没见过，这样的写法都是没问题的，因为数组也是一个对象，可以放在list中。
List转化为数组
List<int[]> list 想转化为list，就可以通过list.toArray()方法直接转化为二维数组。
代码实现
publicint[][] merge(int[][] intervals) {
if (intervals.length==0) {
returnnewint[0][2];
}
if(intervals.length==1) {
returnintervals;
}
//这里是对二维数组按左边界排序
Arrays.sort(intervals, newComparator<int[]>() {
publicintcompare(int[] interval1, int[] interval2) {
returninterval1[0] -interval2[0];
}
});
//把数组装到list中
List<int[]>merged=newArrayList();
intstart=intervals[0][0];
intend =intervals[0][1];
for (inti=0; i<intervals.length;) {
while (++i<intervals.length) {
if (intervals[i][0] >end) {
break;
}
end=Math.max(end, intervals[i][1]);
}
merged.add(newint[]{start, end});
if (i==intervals.length) {
break;
}
start=intervals[i][0];
end=intervals[i][1];
}
//list转为二维数组
returnmerged.toArray(newint[merged.size()][]);
}