如何查找range集合在指定总区间内的空缺范围

你之前搜索的关键词不对，这类问题的标准表述是区间补集计算或者区间缺口查找，英文关键词可搜索range complement、interval gap detection。

通用解法步骤 #

• 第一步：先对输入的已有区间做排序和合并预处理，按区间左端点升序排列，同时合并重叠、相邻的区间，避免脏数据影响计算结果（你示例中的区间已经是有序且无重叠的，生产环境建议保留这一步兼容异常输入）
• 第二步：初始化游标currentStart为你传入的总区间的左端点，同时初始化空数组存储结果
• 第三步：遍历处理好的区间集合：
  • 如果当前遍历到的区间的左端点大于currentStart，说明二者之间存在缺失区间，将[currentStart, 当前区间左端点 - 1]推入结果数组
  • 更新currentStart的值为当前区间右端点 + 1
  • 如果此时currentStart已经大于总区间的右端点，直接终止遍历即可
• 第四步：遍历完成后，如果currentStart仍然小于等于总区间的右端点，说明最后一段区间也是缺失的，将[currentStart, 总区间右端点]推入结果数组

JavaScript实现代码 #

function findMissingRanges(existingRanges, totalRange) {
  const [totalStart, totalEnd] = totalRange;
  // 预处理：排序+合并区间
  const sortedRanges = [...existingRanges].sort((a, b) => a[0] - b[0]);
  const mergedRanges = [];
  for (const range of sortedRanges) {
    if (mergedRanges.length === 0) {
      mergedRanges.push(range);
      continue;
    }
    const last = mergedRanges[mergedRanges.length - 1];
    if (range[0] <= last[1] + 1) {
      // 重叠或相邻则合并
      last[1] = Math.max(last[1], range[1]);
    } else {
      mergedRanges.push(range);
    }
  }

  const result = [];
  let currentStart = totalStart;

  for (const [start, end] of mergedRanges) {
    if (currentStart > totalEnd) break;
    if (start > currentStart) {
      result.push([currentStart, Math.min(start - 1, totalEnd)]);
    }
    currentStart = Math.max(currentStart, end + 1);
  }

  // 处理尾部剩余缺口
  if (currentStart <= totalEnd) {
    result.push([currentStart, totalEnd]);
  }

  return result;
}

// 测试示例
const ranges = [[0,10],[20,30],[40,50]];
const islands = findMissingRanges(ranges, [-10, 60]);
console.log(islands); 
// 输出：[[-10,-1],[11,19],[31,39],[51,60]] 与预期完全匹配

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