以下是 Python3 实现 LeetCode 57. 插入区间 的代码包含详细注释fromtypingimportListclassSolution:definsert(self,intervals:List[List[int]],newInterval:List[int])-List[List[int]]:result[]i0nlen(intervals)# 1. 添加所有在 newInterval 之前且不重叠的区间whileinandintervals[i][1]newInterval[0]:result.append(intervals[i])i1# 2. 合并所有与 newInterval 重叠的区间whileinandintervals[i][0]newInterval[1]:newInterval[0]min(newInterval[0],intervals[i][0])newInterval[1]max(newInterval[1],intervals[i][1])i1result.append(newInterval)# 将合并后的区间加入结果# 3. 添加剩余的区间whilein:result.append(intervals[i])i1returnresult思路说明题目给定一个 无重叠、有序 的区间列表要求插入一个新区间并合并重叠部分返回新的有序无重叠区间列表。由于原始区间已经有序我们可以通过一次线性扫描完成插入和合并时间复杂度为 O(n)。算法分为三步添加前置区间将所有结束位置早于 newInterval 开始位置的区间直接加入结果这些区间与新区间完全无重叠。合并重叠区间当遇到与 newInterval 有重叠的区间即当前区间起点 ≤ newInterval 终点不断更新 newInterval 的起点和终点使其覆盖所有重叠区间。添加剩余区间将剩下的区间直接加入结果。复杂度分析· 时间复杂度O(n)其中 n 为区间数量。只需一次遍历所有区间。· 空间复杂度O(1) 额外空间不考虑结果数组或 O(n) 用于存储结果。
