The idea is to sort the left ends and the right ends separately. Imagine the left ends are like left brackets, the right ends are like right brackets, sorted in a line. We just collect brackets in the ascending order. If the number of right brackets is equal to the number of left brackets, we get a maximal interval. Because sorting integer arrays are fast, this algorithm is under 20ms, beating 96%.

```
public List<Interval> merge(List<Interval> intervals) {
List<Interval> ans = new LinkedList<>();
int l = intervals.size(), k = 0, i = 0, j = 0, start = 0, end;
int[] left = new int[l], right = new int[l];
for (Interval interval : intervals) {
left[k] = interval.start;
right[k++] = interval.end;
}
Arrays.sort(left);
Arrays.sort(right);
// this while loop is like a merge sort, but simpler. We always have j<= i
while (i < l || j < l) {
if (i == j && i < l) start = left[i++]; // start a new interval
if (i < l && left[i] <= right[j]) i++;
else {
end = right[j++];
if (j == i) ans.add(new Interval(start, end)); // If i == j, the current interval can not be extended
}
}
return ans;
}
```