合并区间
题目描述:
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。 提示: 1 <= intervals.length <= 10^4 intervals[i].length == 2 0 <= starti <= endi <= 10^4
class Solution {
public int[][] merge(int[][] intervals) {
int len = intervals.length;
List<int[]> result = new ArrayList<int[]>(); // 由于最终的区间数不固定
Arrays.sort(intervals,new Comparator<int[]>(){ // 按照开始区间的开始位置作为排序标准
public int compare(int[] a , int[] b){
return a[0]-b[0];
}
});
for(int i = 0 ; i<len ; i++){
// 获取当前的区间
int x = intervals[i][0];
int y = intervals[i][1];
int[] temp = new int[2];
temp[0] = x;
temp[1] = y;
// 以下只有两种可能:要么连续要么离散
if(i+1<len && temp[1]>=intervals[i+1][0]){ // 连续的情况下
while(i+1<len && temp[1]>=intervals[i+1][0]){
temp[1] = (temp[1]>intervals[i+1][1])?temp[1]:intervals[i+1][1];
i++;
}
}
result.add(temp); // 这里最终都要变为离散情况
}
return result.toArray(new int[result.size()][2]);
}
}
这里刚开始会有点想不到,也就是预处理步骤:将intervals数组按照第一列的值从小到大排序。排完序后,就容易分析了,准备一张草稿纸,随便画上几行线段,可以发现只有合并的情况只有一种情况(即当前的区间的右边界值大于等于下一个区间的左边界值时):这时候只要不断更新右边界值即可,使之一直保持最大。然后还有一种是断层的状态(即当前的区间右边界值小于下一个区间的左边界值):这个时候可以将当前区间直接放入result数组中。详细请看代码,有疑问的地方欢迎读者留言。