“合并区间”问题解析及其思考

合并区间

题目

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

解析

本题思路相对比较容易想

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

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

1. 第一个作为基准

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

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

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

对二维数组进行排序

我们知道对一维数组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()][]);

}