太原做网站需要多少钱,做游戏的外包网站,扁平化设计网站,微信小程序制作个人版题目#xff1a;
以数组 intervals 表示若干个区间的集合#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间#xff0c;并返回 一个不重叠的区间数组#xff0c;该数组需恰好覆盖输入中的所有区间 。
示例 1#xff1a;
输入#xff…题目
以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。
示例 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] 可被视为重叠区间。
提示
1 intervals.length 104 intervals[i].length 2 0 starti endi 104
思路
本题的本质其实还是判断重叠区间问题。跟452. 用最少数量的箭引爆气球和435. 无重叠区间一个套路详细思路见力扣452. 用最少数量的箭引爆气球贪心 按照此套路做完后会发现本题还有一个难点就是如何合并区间合并前的区间该如何处理呢这里直接把结果集写进新数组中在新数组中进行去重即可 代码如下 result [intervals[0]] # 初始化结果列表将第一个区间加入其中for i in range(1, len(intervals)):# 如果当前区间的起始位置小于等于结果列表中最后一个区间的结束位置说明有重叠if result[-1][1] intervals[i][0]:# 更新结果列表中最后一个区间的结束位置为当前区间的结束位置和原结束位置的最大值result[-1][1] max(result[-1][1], intervals[i][1])else:# 如果没有重叠将当前区间加入结果列表中result.append(intervals[i])完整代码
class Solution:def merge(self, intervals: List[List[int]]) - List[List[int]]:# 按区间起始位置排序intervals.sort(key lambda x : x[0])result [intervals[0]] # 初始化结果列表将第一个区间加入其中for i in range(1, len(intervals)):# 如果当前区间的起始位置小于等于结果列表中最后一个区间的结束位置说明有重叠if result[-1][1] intervals[i][0]:# 更新结果列表中最后一个区间的结束位置为当前区间的结束位置和原结束位置的最大值result[-1][1] max(result[-1][1], intervals[i][1])else:# 如果没有重叠将当前区间加入结果列表中result.append(intervals[i])return result
