算法系列—scan line 算法(2)
今天通过两个题巩固一下之前我们学过区间的算法，一个是将一个区间插入到有序区间数组，并且进行适当处理，另一个是移除一个区间，主要注意移除需要考虑不同情况。
插入一个区间到一个区间序列
57. Insert Interval 复制代码
给你一个不重叠的区间数组，其中区间[i]=[starti, endi] 表示第i个区间的开始和结束，区间按 start 升序排序。还给你一个区间 newInterval = [start, end]，要将newInterval 插入区间，使区间仍按 start 的升序排序，且区间中没有任何重叠的区间（必要时合并重叠的区间）。
// 已有区间序列和插入区间序列 let intervalsList = [[1,3],[6,9]] let newInterval = [2,5] //output [[1,5],[6,9]] function insert(intervalsList, newInterval){ // 创建空数组作为结果序列 let res = []; // 遍历区间序列 for (let i = 0; i < intervalsList.length; i++) { //获取当前值 let cur = intervalsList[i]; //如果当前区间的结束值小于新区间的起始值，则将当前区间放入到结果，还没到需要插入新区间时刻 if(newInterval == null || cur[1] < newInterval[0]){ res.push(cur) //如果当前区间的开始值大于新区间的结束值， //按顺序，首先将新区间插入结果序列，然后再将当前区间插入到序列，并且将新区间更新为 null 随后不再处理新区间 }else if(cur[0] > newInterval[1]){ res.push(newInterval); res.push(cur); newInterval = null //如果当前区间和新区间存在 overlapping,将其合并，合并后区间的起始值为两者起始值最小，结束值为两者结束值最大作为起始和结束值 }else{ newInterval[0] = Math.min(newInterval[0],cur[0]); newInterval[1] = Math.max(newInterval[1],cur[1]); } } //最后判断 newInterval 如果不为 null 则将其插入到结果序列 if(newInterval !=null) res.push(newInterval); return res } console.log(insert(intervalsList,newInterval)) 复制代码移除一个区间
给定一个数组i ntervals，其中intervals[i]=[li, ri]代表区间 [li, ri]，移除所有被列表中另一个区间覆盖的区间。区间[a, b]被区间[c, d]覆盖，当且仅当c<=a，b<=d。
let intervalsList = [[0,2],[3,4],[5,7]]; let toBeRemoved = [1,6] function remove(intervalsList,toBeRemoved){ // 创建空数组作为结果序列 //算法系列—扫描线算法(2) //介绍使用如何解决区间插入和区间移除的问题 let res = [] // 遍历序列 for (let i = 0; i < intervalsList.length; i++) { // 获取序列中一个区间 let cur = intervalsList[i]; // 如果当前空间和要移除的区间没有个 overlapping 则将当前区间加入到结果序列 if(cur[1] <= toBeRemoved[0] || cur[0] > toBeRemoved[1]){ res.push(cur) }else{ //如果有 overlapping 并且当前区间开始值小于要移除区间的开始值，则保留区间为[当前区间起始值, 要移除区间起始值] if(cur[0] < toBeRemoved[0]){ res.push([cur[0],toBeRemoved[0]]) } //如果有 overlapping 并且当前区间结束值大于要移除区间的结束值，则保留区间为[要移除区间结束值,当前区间结束值] if(cur[1]> toBeRemoved[1]){ res.push([toBeRemoved[1],cur[1]]) } } } return res } console.log(remove(intervalsList,toBeRemoved))
作者：ti138729
链接：https://juejin.cn/post/7018518064001974302