07.合并连续区间
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
空间复杂度
O
(
l
o
g
n
)
O(logn)
O
(
l
o
g
n
)
- 对所有区间, 按照左端点从小到大排序.
- 首先将排序后的第一个区间放入ans数组.
-
对之后的每一个区间, 依次判断,
- 若左端点小于ans数组中最后一个区间的右端点, 则合并这两个区间;
- 否则, 将该区间加入ans数组末尾.
时间复杂度上, 排序的时间复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
, 遍历区间的时间复杂度为
O
(
n
)
O(n)
O
(
n
)
, 故时间花费主要取决于排序, 即
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
.
空间复杂度上, 排序的空间复杂度为
O
(
l
o
g
n
)
O(logn)
O
(
l
o
g
n
)
.