LeetCode 56. Merge Intervals 题解

LeetCode 56. Merge Intervals 题解

题目描述

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

解题思路

方法：排序

思路：

• 首先按照每个区间的起始位置进行排序
• 初始化一个结果数组，将第一个区间加入结果数组
• 遍历剩余的区间：
  • 获取结果数组中最后一个区间的结束位置
  • 如果当前区间的起始位置小于等于最后一个区间的结束位置，说明两个区间重叠，需要合并
  • 更新最后一个区间的结束位置为两个区间结束位置的最大值
  • 否则，将当前区间加入结果数组

复杂度分析：

• 时间复杂度：O(n log n)，其中 n 是区间的数量。排序的时间复杂度是 O(n log n)，遍历的时间复杂度是 O(n)。
• 空间复杂度：O(n)，其中 n 是区间的数量。需要一个数组来存储结果。

代码实现

方法：排序

class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: if not intervals: return [] # 按照区间的起始位置排序 intervals.sort(key=lambda x: x[0]) result = [intervals[0]] for i in range(1, len(intervals)): current_interval = intervals[i] last_interval = result[-1] # 如果当前区间的起始位置小于等于最后一个区间的结束位置，说明两个区间重叠 if current_interval[0] <= last_interval[1]: # 更新最后一个区间的结束位置为两个区间结束位置的最大值 last_interval[1] = max(last_interval[1], current_interval[1]) else: # 否则，将当前区间加入结果数组 result.append(current_interval) return result

测试用例

测试用例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]

测试用例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]

测试用例 3：

输入：intervals = [[1,4],[0,4]]
输出：[[0,4]]

测试用例 4：

输入：intervals = [[1,4],[2,3]]
输出：[[1,4]]

总结

本题是区间合并的经典问题，主要考察对区间排序和遍历的理解。通过先排序，然后遍历合并重叠的区间，我们可以有效地解决这个问题。

排序的核心思想是将区间按照起始位置排序，这样在遍历过程中，我们只需要比较当前区间和结果数组中最后一个区间的结束位置，就可以判断是否需要合并。

这种方法不仅适用于区间合并问题，还可以应用于许多其他需要处理区间的问题，例如区间交集、区间覆盖等。掌握区间处理的技巧，对于解决这类问题非常重要。