The basic idea is sorting the intervals by its start. Then compare intervals[i]'s start with intervals[i-1]'s end, merge the overlapping intervals correspondingly. As the following:

**Time complexity=** **O(nlgn)** for sorting **+ O(n)** for merging = O(nlgn + n) = **O(nlgn)**

```
public List<Interval> merge(List<Interval> intervals) {
List<Interval>res = new ArrayList<Interval>();
if (intervals == null || intervals.isEmpty()) return res;
Collections.sort(intervals, new Comparator<Interval>(){
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;// Sort ascendingly by interval's start
}
});
Interval last = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval cur = intervals.get(i);
if (cur.start <= last.end) {
last.end = Math.max(cur.end, last.end);
} else {
res.add(last);
last = cur;
}
}
res.add(last);// Add the last interval
return res;
}
```