企业官网建设流程全解析

以下是 Python3 实现 LeetCode 57. 插入区间 的代码，包含详细注释：

fromtypingimportListclassSolution:definsert(self,intervals:List[List[int]],newInterval:List[int])->List[List[int]]:result=[]i=0n=len(intervals)# 1. 添加所有在 newInterval 之前且不重叠的区间whilei<nandintervals[i][1]<newInterval[0]:result.append(intervals[i])i+=1# 2. 合并所有与 newInterval 重叠的区间whilei<nandintervals[i][0]<=newInterval[1]:newInterval[0]=min(newInterval[0],intervals[i][0])newInterval[1]=max(newInterval[1],intervals[i][1])i+=1result.append(newInterval)# 将合并后的区间加入结果# 3. 添加剩余的区间whilei<n:result.append(intervals[i])i+=1returnresult

思路说明

题目给定一个 无重叠、有序 的区间列表，要求插入一个新区间并合并重叠部分，返回新的有序无重叠区间列表。由于原始区间已经有序，我们可以通过一次线性扫描完成插入和合并，时间复杂度为 O(n)。

算法分为三步：

1. 添加前置区间：将所有结束位置早于 newInterval 开始位置的区间直接加入结果（这些区间与新区间完全无重叠）。
2. 合并重叠区间：当遇到与 newInterval 有重叠的区间（即当前区间起点 ≤ newInterval 终点），不断更新 newInterval 的起点和终点，使其覆盖所有重叠区间。
3. 添加剩余区间：将剩下的区间直接加入结果。

复杂度分析

· 时间复杂度：O(n)，其中 n 为区间数量。只需一次遍历所有区间。
· 空间复杂度：O(1) 额外空间（不考虑结果数组），或 O(n) 用于存储结果。