以下是 LeetCode 57「插入区间」的 TypeScript 实现。思路由于原区间列表已经按起点排序且无重叠我们只需要遍历一次把完全在 newInterval 左边、没有交集的区间直接加入结果。遇到与 newInterval 有交集的区间就不断合并更新 newInterval 的左右端点。合并结束后把 newInterval 加入结果。把剩下的区间直接加入结果。复杂度· 时间复杂度O(n)只遍历一次区间列表。· 空间复杂度O(n)结果数组所需空间。TypeScript 代码functioninsert(intervals:number[][],newInterval:number[]):number[][]{constresult:number[][][];leti0;constnintervals.length;// 1. 将所有在 newInterval 左边且无重叠的区间加入结果while(inintervals[i][1]newInterval[0]){result.push(intervals[i]);i;}// 2. 合并所有与 newInterval 重叠的区间while(inintervals[i][0]newInterval[1]){newInterval[0]Math.min(newInterval[0],intervals[i][0]);newInterval[1]Math.max(newInterval[1],intervals[i][1]);i;}result.push(newInterval);// 3. 将剩余区间加入结果while(in){result.push(intervals[i]);i;}returnresult;}测试示例console.log(insert([[1,3],[6,9]],[2,5]));// 输出[[1,5],[6,9]]console.log(insert([[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8]));// 输出[[1,2],[3,10],[12,16]]
以下是 LeetCode 57「插入区间」的 TypeScript 实现。思路由于原区间列表已经按起点排序且无重叠我们只需要遍历一次把完全在 newInterval 左边、没有交集的区间直接加入结果。遇到与 newInterval 有交集的区间就不断合并更新 newInterval 的左右端点。合并结束后把 newInterval 加入结果。把剩下的区间直接加入结果。复杂度· 时间复杂度O(n)只遍历一次区间列表。· 空间复杂度O(n)结果数组所需空间。TypeScript 代码functioninsert(intervals:number[][],newInterval:number[]):number[][]{constresult:number[][][];leti0;constnintervals.length;// 1. 将所有在 newInterval 左边且无重叠的区间加入结果while(inintervals[i][1]newInterval[0]){result.push(intervals[i]);i;}// 2. 合并所有与 newInterval 重叠的区间while(inintervals[i][0]newInterval[1]){newInterval[0]Math.min(newInterval[0],intervals[i][0]);newInterval[1]Math.max(newInterval[1],intervals[i][1]);i;}result.push(newInterval);// 3. 将剩余区间加入结果while(in){result.push(intervals[i]);i;}returnresult;}测试示例console.log(insert([[1,3],[6,9]],[2,5]));// 输出[[1,5],[6,9]]console.log(insert([[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8]));// 输出[[1,2],[3,10],[12,16]]
