[LeetCode] Merge Intervals (Java)

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].


We can sort the intervals first. They are sorted by their “start” value. If the “start” value is the same, “end” value is used to compare them. In Java, it’s very easy to sort them by writing a comparator.



Sorting costs $O(nlogn)$. And merging the sorted intervals costs $O(n)$. So the complexity is $O(nlogn)$.