56. 合并区间¶
题目¶
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1:
输入:
intervals = [[1,3],[2,6],[8,10],[15,18]]输出:
[[1,6],[8,10],[15,18]]解释: 区间
[1,3]和[2,6]重叠, 将它们合并为[1,6].
示例 2:
输入:
intervals = [[1,4],[4,5]]输出:
[[1,5]]解释: 区间
[1,4]和[4,5]可被视为重叠区间。
题解¶
Go
func merge(intervals [][]int) (ans [][]int) {
slices.SortFunc(intervals, func(p, q []int) int { return p[0] - q[0] }) // 按照左端点从小到大排序
for _, p := range intervals {
m := len(ans)
if m > 0 && p[0] <= ans[m-1][1] { // 可以合并
ans[m-1][1] = max(ans[m-1][1], p[1]) // 更新右端点最大值
} else { // 不相交，无法合并
ans = append(ans, p) // 新的合并区间
}
}
return
}
Python
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda p: p[0]) # 按照左端点从小到大排序
ans = []
for p in intervals:
if ans and p[0] <= ans[-1][1]: # 可以合并
ans[-1][1] = max(ans[-1][1], p[1]) # 更新右端点最大值
else: # 不相交，无法合并
ans.append(p) # 新的合并区间
return ans
复杂度¶
- 时间复杂度: \(O(n \ logn)\)，其中 \(n\) 是 \(intervals\) 的长度。
- 空间复杂度: \(O(1)\)。