LeetCode 题解工作台
合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start i , end i ] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。 示例 1： 输入： intervals = [[1,3],[2,6],[…
2
题型
9
代码语言
3
相关题
当前训练重点
中等 · 数组·排序
答案摘要
我们可以将区间按照左端点升序排列，然后遍历区间进行合并操作。 具体的合并操作如下。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·排序 题型思路
题目描述
以数组 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 <= 104intervals[i].length == 20 <= starti <= endi <= 104
解题思路
方法一：排序 + 一次遍历
我们可以将区间按照左端点升序排列，然后遍历区间进行合并操作。
具体的合并操作如下。
我们先将第一个区间加入答案，然后依次考虑之后的每个区间：
- 如果答案数组中最后一个区间的右端点小于当前考虑区间的左端点，说明两个区间不会重合，因此我们可以直接将当前区间加入答案数组末尾；
- 否则，说明两个区间重合，我们需要用当前区间的右端点更新答案数组中最后一个区间的右端点，将其置为二者的较大值。
最后，我们返回答案数组即可。
时间复杂度 ，空间复杂度 。其中 为区间个数。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
ans = []
st, ed = intervals[0]
for s, e in intervals[1:]:
if ed < s:
ans.append([st, ed])
st, ed = s, e
else:
ed = max(ed, e)
ans.append([st, ed])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if you sort intervals before merging, as failing to sort leads to incorrect merges.
- question_mark
Looks for a clean in-place or linear pass after sorting, showing understanding of array traversal and comparison.
- question_mark
Wants explanation of edge cases where intervals share endpoints or fully overlap.
常见陷阱
外企场景- error
Failing to sort intervals first, causing incorrect overlap detection.
- error
Not updating the end of merged intervals correctly, leading to incomplete merges.
- error
Ignoring cases where intervals touch but do not strictly overlap, e.g., [1,4] and [4,5].
进阶变体
外企场景- arrow_right_alt
Merge intervals with additional interval insertion, testing dynamic updates to merged lists.
- arrow_right_alt
Merge intervals using linked list structure instead of array, emphasizing pointer manipulation.
- arrow_right_alt
Count overlapping intervals without merging, focusing on interval coverage rather than consolidation.