以下是 Rust 实现 LeetCode 57. 插入区间 的代码包含详细注释implSolution{pubfninsert(intervals:VecVeci32,new_interval:Veci32)-VecVeci32{letmutresult:VecVeci32Vec::new();letmuti0;letnintervals.len();letmutnew_intervalnew_interval;// 使新区间可变用于合并更新// 1. 添加所有在 new_interval 之前且不重叠的区间whileinintervals[i][1]new_interval[0]{result.push(intervals[i].clone());i1;}// 2. 合并所有与 new_interval 重叠的区间whileinintervals[i][0]new_interval[1]{new_interval[0]new_interval[0].min(intervals[i][0]);new_interval[1]new_interval[1].max(intervals[i][1]);i1;}result.push(new_interval);// 将合并后的区间加入结果// 3. 添加剩余的区间whilein{result.push(intervals[i].clone());i1;}result}}思路说明题目给定一个 无重叠、有序 的区间列表要求插入一个新区间并合并所有重叠部分返回新的有序无重叠区间列表。由于原始区间已经按起点排序我们可以通过一次线性扫描完成插入和合并时间复杂度为 O(n)。算法分为三步添加前置区间将所有结束位置严格早于 new_interval 开始位置的区间直接加入结果这些区间与新区间完全无重叠。合并重叠区间当遇到与 new_interval 有重叠的区间即当前区间起点 ≤ new_interval 终点不断更新 new_interval 的起点和终点使其覆盖所有重叠区间。更新后直接加入结果。添加剩余区间将剩下的区间直接加入结果。复杂度分析· 时间复杂度O(n)其中 n 为区间数量。每个区间最多被访问一次。· 空间复杂度O(n)结果数组或 O(1) 额外空间不包括结果存储。
