DeepSeek LeetCode 56. 合并区间 Rust实现

以下是 Rust 实现 LeetCode 56. 合并区间 的代码包含详细注释implSolution{pubfnmerge(intervals:VecVeci32)-VecVeci32{// 空输入直接返回空结果ifintervals.is_empty(){returnvec![];}// 按区间的起点进行排序letmutintervalsintervals;intervals.sort_unstable_by_key(|v|v[0]);// 结果数组letmutmerged:VecVeci32Vec::new();// 当前正在合并的区间初始为第一个区间letmutcurrentintervals[0].clone();// 从第二个区间开始遍历forintervalinintervals.into_iter().skip(1){// 如果当前区间的起点 正在合并区间的终点说明有重叠ifinterval[0]current[1]{// 更新终点为两者较大值current[1]current[1].max(interval[1]);}else{// 无重叠将当前区间加入结果并开始合并新区间merged.push(current);currentinterval;}}// 最后一个区间加入结果merged.push(current);merged}}思路说明排序按区间起点升序排序保证可以线性扫描合并。合并逻辑· 维护一个 current 表示当前正在合并的区间。· 遍历后续区间若其起点 ≤ current 的终点则更新 current 的终点为两者终点的较大值。· 否则说明无重叠将 current 放入结果并将当前区间设为新的 current。收尾遍历结束后将最后一个 current 放入结果。复杂度· 时间复杂度O(n log n)主要开销在排序。· 空间复杂度O(n)结果数组或 O(log n)排序栈空间取决于实现。