【leetcode复健-12】56. 合并区间-排序

56. 合并区间 - 力扣（LeetCode）

以数组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] 可被视为重叠区间。

示例 3：

输入：intervals = [[4,7],[1,4]]输出：[[1,7]]解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

题目分析

给定一串区间，要求我们合并所有有交集的区间，并返回最终所有最终合并的区间。
这题合并区间的思路非常好想，对于两个有交集的区间，左边界取最小，右边界取最大即可。
这题的难点在于给定的区间是无序的，这就导致我们很难匹配出具有交集的区间。解决办法其实非常简单。既然无序的区间查找起来很困难，那我们只需要让他们变得有序即可。

解决思路

我们按照每个区间的左边界进行排序，只需要使用.sort() 加 lambda 表达式就可以完成，之后遍历我们只需要关心相邻两个区间的右边界与左边界大小关系即可。
使用一个列表存放我们最总的合并区间，对于排序后的列表的相邻两个区间，如果左区间的右端点小于有区间左端点则将当前区间存入最终答案，开始合并下一个区间。

代码展示

class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda x: x[0]) # 按左端点排序 merged = [intervals[0]] # 第一个区间直接入结果 for s, e in intervals[1:]: if s <= merged[-1][1]: # 与最后一个已合并区间重叠 merged[-1][1] = max(merged[-1][1], e) # 只扩右端点 else: # 彻底断开 merged.append([s, e]) return merged