合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start, end]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

约定

• 按区间起点升序排序后合并。
• 两个区间只要有重叠就合并（包括端点相接，如 [1,3] 与 [3,5] 合并为 [1,5]）。
• 结果按区间起点升序排列。

输入

• intervals：区间数组，长度 [1, 10^4]，start <= end。

输出

合并后的区间数组，按起点升序。

示例一

输入：

intervals = [[1,3],[2,6],[8,10],[15,18]]

输出：

[[1,6],[8,10],[15,18]]

示例二

输入：

intervals = [[1,4],[4,5]]

输出：

[[1,5]]

复杂度要求

• 时间 O(n log n)，空间 O(n)。