Given a collection of closed intervals, merge all overlapping intervals and return the resulting list. Intervals that share an endpoint (e.g. [1,4] and [4,5]) are considered overlapping.
Input
intervals: an array of intervals, each [start, end] with start <= end
Output
An array of merged, non-overlapping intervals sorted by start.
Examples
Example 1
Inputintervals = [[1,6],[2,6],[8,10],[15,18]]
Output[[1,6],[8,10],[15,18]]
Example 2
Inputintervals = [[1,5],[4,5]]
Output[[1,5]]
Constraints
intervals[i][0] <= intervals[i][1]
The input may be in any order.