Merge Intervals

Problem Given a collection of intervals, merge all overlapping intervals and return the resulting non-overlapping intervals covering the same ranges.

Input / Output

• Input: a list of intervals [start, end].
• Output: the merged list of disjoint intervals, sorted by start.

Constraints

• 1 <= n <= 10^4.
• Intervals may be given in any order; touching intervals (e.g. [1,3],[3,5]) are usually considered overlapping — clarify.

Example

• [[1,3],[2,6],[8,10],[15,18]] -> [[1,6],[8,10],[15,18]]
• [[1,4],[4,5]] -> [[1,5]]