JavaScript如何实现多维数组中相近区间的检测与合并替换

假设我们有一个由双元素数组[from, to]表示的区间组成的List集合。
当我们添加类似[5,8]的新区间数组时，需要在List中检测是否存在被新区间覆盖或相邻的相近区间，并用新的区间值合并替换原有区间，具体示例如下：

示例1 #

var List = [[1,2], [3,4], [6,7], [9,10]]
var newData = [5,8]

预期输出：
[[1,2], [3,4], [5,8], [9,10]]
原有的[6,7]区间已完全包含在新的[5,8]区间内，因此被替换。

示例2 #

var List = [[1,3], [4,6], [8,10]]
var newData = [5,9]

预期输出：

[[1,3], [4,10]]

原有的[4,6]、[8,10]区间与新插入的[5,9]区间重叠相邻，因此合并为[4,10]。

核心思路是先合并所有区间再按左端点排序，遍历过程中直接合并重叠/相邻区间即可，代码如下：

function mergeInterval(originList, newInterval) {
  // 合并新旧区间
  const allIntervals = [...originList, newInterval]
  // 按区间左端点从小到大排序
  allIntervals.sort((a, b) => a[0] - b[0])
  
  const result = [allIntervals[0]]
  for(let i = 1; i < allIntervals.length; i++) {
    const current = allIntervals[i]
    const lastMerged = result[result.length - 1]
    // 判断是否重叠/相邻，不需要合并相邻场景可以去掉+1
    if(current[0] <= lastMerged[1] + 1) {
      // 合并区间，右端点取两者最大值
      lastMerged[1] = Math.max(lastMerged[1], current[1])
    } else {
      result.push(current)
    }
  }
  return result
}

测试验证 #

// 测试示例1
const list1 = [[1,2], [3,4], [6,7], [9,10]]
console.log(mergeInterval(list1, [5,8])) 
// 输出 [[1,2], [3,4], [5,8], [9,10]]

// 测试示例2
const list2 = [[1,3], [4,6], [8,10]]
console.log(mergeInterval(list2, [5,9]))
// 输出 [[1,3], [4,10]]

内容的提问来源于stack exchange，提问作者Alexey