Merge Intervals

Problem Given a collection of intervals, merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the input.

Input / Output

• Input: an array of intervals, each [start, end].
• Output: the merged, non-overlapping intervals, sorted by start.

Constraints

• 1 ≤ n ≤ 10^4.
• Intervals may be given in any order; two intervals overlap when one's start is ≤ the other's end (touching intervals like [1,3] and [3,5] merge).

Example

• [[1,3],[2,6],[8,10]] → [[1,6],[8,10]] ([1,3] and [2,6] merge into [1,6]).
• [[1,4],[4,5]] → [[1,5]] (touching intervals merge).