Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18]
,
return [1,6],[8,10],[15,18]
.
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
// Start typing your Java solution below
// DO NOT write main() function
if(intervals==null||intervals.size()<=1){
return intervals;
}
//sort the intervals by the start time.
//1. convert ArrayList to array
Interval[] intervalArr = new Interval[intervals.size()];
int index = 0;
for(Interval interval:intervals){
intervalArr[index++] = interval;
}
//2. use quick sort to sort intervals by the start time O(nlgn)
sort(intervalArr,0,intervalArr.length-1);
//3. only need to compare the new interval with the last interval in the sorted list
ArrayList<Interval> merged = new ArrayList<Interval>();
Interval last = intervalArr[0];
for(int i=1;i<intervalArr.length;i++){
if(last.end<intervalArr[i].start){
merged.add(last);
last = intervalArr[i];
}else{
Interval newInterval = new Interval(last.start, Math.max(last.end, intervalArr[i].end));
last = newInterval;
}
}
merged.add(last);
return merged;
}
public void sort(Interval[] inters,int start, int end){
int pivot = partition(inters, start, end);
if(start<pivot-1){
sort(inters, start, pivot-1);
}
if(pivot<end){
sort(inters, pivot, end);
}
}
public int partition(Interval[] inters, int start, int end){
int middle = (start+end)/2;
Interval pivot = inters[middle];
int i=start;
int j=end;
while(i<=j){
while(inters[i].start<pivot.start){
i++;
}
while(inters[j].start>pivot.start){
j--;
}
if(i<=j){
swap(inters,i,j);
i++;
j--;
}
}
return i;
}
public void swap(Interval[] inters, int i, int j){
Interval tmp = inters[i];
inters[i] = inters[j];
inters[j] = tmp;
}
}
So the overall time complexity is O(nlgn)