56.?合并區(qū)間
以數(shù)組?
intervals?表示若干個(gè)區(qū)間的集合，其中單個(gè)區(qū)間為?intervals[i] = [starti, endi]?。請(qǐng)你合并所有重疊的區(qū)間，并返回?一個(gè)不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間?。示例 1：
輸入：intervals = [[1,3],[2,6],[8,10],[15,18]] 輸出：[[1,6],[8,10],[15,18]] 解釋：區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].示例?2：
輸入：intervals = [[1,4],[4,5]] 輸出：[[1,5]] 解釋：區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104通過(guò)次數(shù)
701.1K
提交次數(shù)
1.4M
通過(guò)率
49.6%文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-707097.html
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
time: O(nlogn) 主要由排序操作決定，其中 n 是區(qū)間的個(gè)數(shù)。
space: O(n) 用于存儲(chǔ)結(jié)果區(qū)間。
"""
result = []
# base case: 區(qū)間集合為空直接返回
if not intervals:
return result
# 按區(qū)間的起始點(diǎn)進(jìn)行排序
intervals.sort(key=lambda x: x[0])
result.append(intervals[0]) # 第一個(gè)區(qū)間可以直接放入結(jié)果集中
for i in range(1, len(intervals)):
current_start, current_end = intervals[i]
last_start, last_end = result[-1]
# 如果當(dāng)前區(qū)間與結(jié)果列表中的最后一個(gè)區(qū)間不重疊，則將當(dāng)前區(qū)間添加到結(jié)果列表中
if current_start > last_end:
result.append([current_start, current_end]) # intervals[i]也可以
else:
# 否則，合并這兩個(gè)區(qū)間
# 合并只需更新結(jié)果集最后一個(gè)區(qū)間的右邊界，因?yàn)楦鶕?jù)排序，左邊界已經(jīng)是最小的
result[-1][1] = max(current_end, last_end)
return result ?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-707097.html
到了這里，關(guān)于Day 36 貪心算法 part05 ： 435. 無(wú)重疊區(qū)間 763.劃分字母區(qū)間 56. 合并區(qū)間的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
