# A real O(NlogN) solution bases on Java

• My solution uses sort first, and uses divide and conquer to merge the Interval.

The most popular solution for this problem is not real O(NlogN), because their remove method for merging will cause O(N2).

The time complexity of my solution is real O(NlogN), but the disadvantage is that the space complexity is big. This is the disadvantage of divide and conquer and merger sort.

``````public List<Interval> merge(List<Interval> intervals) {

if (intervals.size()==0) return new ArrayList<Interval>();

Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start-o2.start;
}
});

List<Interval> result = this.divide(intervals);

return result;

}

private List<Interval> divide(List<Interval> intervals) {

if (intervals.size()==1)
return intervals;

int size = intervals.size()/2;

List<Interval> left = new ArrayList<>();
List<Interval> right = new ArrayList<>();

for (int i = 0; i < size; i++){
}

for (int i = size; i < intervals.size(); i++){
}

left = this.divide(left);
right = this.divide(right);

List<Interval> result = new ArrayList<>();

Interval leftEnd = left.remove(left.size()-1);
int i = 0;
for (; i < right.size(); i++){
Interval rightTemp = right.get(i);
if ( rightTemp.start<=leftEnd.end && rightTemp.end<=leftEnd.end ){
continue;
}
else if ( rightTemp.start<=leftEnd.end && rightTemp.end>leftEnd.end ){
leftEnd = new Interval(leftEnd.start, rightTemp.end);
i++;
break;
}
else{
break;
}
}

for (int j = 0; j < left.size(); j++){