合并区间(python3)
合并区间
- 题目描述
- 解题思路
- 代码实现
- 复杂度
题目描述
以数组 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]可被视为重叠区间。
解题思路
先将题目的核心问题提取出来，变成单个的数学问题。即合并区间的条件是，若第二个数组的左区间小于等于第一个数组的右区间，则说明这两个数组区间能够合并。
由于输入列表无序，先按子数组的第一个数字升序排列，这可以保证遍历时不会漏掉区间。以当前数组为对比，如果有满足条件的区间出现，更新当前数组的右区间，取二者的较大值。
通过标记数组记录已合并的区间，用于减少时间复杂度。
代码实现
def merge(self, intervals: List[List[int]]) -> List[List[int]]:n = len(intervals)flag = [0]*nk = 0res = []sorted_intervals = sorted(intervals, key=lambda x: x[0])# print(sorted_intervals)for interval in sorted_intervals:if flag[k]==1:k+=1continueleft = interval[0]right = interval[1]temp = []temp.append(left)i = kwhile i<n:if sorted_intervals[i][0]<=right:right = max(right,sorted_intervals[i][1])flag[i] = 1i+=1temp.append(right)res.append(temp)k+=1return res
复杂度
时间复杂度：O（NLogN）