问题描述
https://leetcode.com/problems/merge-intervals/
解决思路
先将所给的每个数组，按照首元素进行排序，然后分情况讨论：
- 上一个数组首元素等于当前数组首元素的时候，若上一个数组的尾元素小于当前数组尾元素，则将当前数组尾元素，设置为新数组的尾元素。
- 上一个数组首元素小于当前数组首元素的时候，分下面的情况：
2.1 上一个数组的尾元素，小于当前数组的首元素，则将当前数组首元素和尾元素设置为新数组首尾元素。
2.2 上一个数组的尾元素大于当前数组的尾元素，并且上一个数组尾元素小于当前数组尾元素时，用当前数组尾元素作为新数组尾元素。
代码
class Solution {
public int[][] merge(int[][] intervals) {
//corner case
if(intervals.length <= 1) return intervals;
//sort all intervals according to the start value
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
List<int[]> result = new ArrayList<>();
//put the first interval into the result list
result.add(intervals[0]);
//record the index of last interval in the list
int lastIntervalIndex = 0;
for(int i = 0; i < intervals.length; i++){
//get the start and end of last merging interval
int lastStart = result.get(lastIntervalIndex)[0];
int lastEnd = result.get(lastIntervalIndex)[1];
//the start and end of the inteval which will be merged
int curStart = intervals[i][0];
int curEnd = intervals[i][1];
//if the two start are polymerized
if(lastStart == curStart){
if(curEnd > lastEnd){
result.set(lastIntervalIndex, new int[] {curStart, curEnd});
}
}else{//if the two start are not polymerized
if(curStart > lastEnd){//if the start of current interval is larger than the start of the last interval, which means they have no Overlapping part
result.add(new int[] {curStart, curEnd});
lastIntervalIndex++;
}else if(curEnd > lastEnd){//if the start of current interval is no larger than the start of the last interval, which means they have some overlapping part
result.set(lastIntervalIndex, new int[]{lastStart, curEnd});
}
}
}
return result.toArray(new int[0][]);
}
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
