Merge Overlapping Intervals in O(n log n) Time

meta Given a collection of intervals, merge all overlapping intervals. For example, for intervals [[1,3],[2,6],[8,10],[15,18]], return [[1,6],[8,10],[15,18]]. The algorithm should have a time complexity of O(n log n). Example Input [[1,3],[2,6],[8,10],[15,18]]