# Java sol, inspired by Russian doll

• Inspired by TianhaoSong's Russian doll envelope solution,

1. sort the list, start ascending and end descending, e.g. [1, 2], [3,4], [2, 4], [2,6], [2, 7] becomes [1, 2], [2, 7], [2, 6], [2, 4], [3, 4]
2. then scan and merge the array. Ignore interval with same start, just check the code and it's quite clear.
``````/**
* 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 List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.size() <= 1) {
return intervals;
}
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval i1, Interval i2) {
if (i1.start == i2.start) {
return i2.end - i1.end;// end descending
}
return i1.start - i2.start;// start ascending
}
});
Interval pt = new Interval(intervals.get(0).start, intervals.get(0).end);
for (int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (pt.start == curr.start) {
continue;
}
if (pt.end >= curr.start) {
pt.end = Math.max(pt.end, curr.end);
} else {
pt = new Interval(curr.start, curr.end);
}
}