React/JavaScript：提交时如何检查数组中数值范围无重叠

问题背景 #

我需要校验一组包含startAddress和endAddress的地址范围列表，确保所有范围既不重复也不重叠。示例数据如下：

[
  {
    "id": 23,
    "startAddress": 10,
    "endAddress": 15
  },
  {
    "id": 24,
    "startAddress": 11,
    "endAddress": 13
  },
  {
    "id": 25,
    "startAddress": 21,
    "endAddress": 23
  }
]

我之前写的代码只能检测完全相同的范围，无法识别重叠情况（比如1-5和2-6这类重叠范围会被错误放行）：

const findDuplicateRanges = data => {
    const addressRanges = new Map() 
    for (const item of data) {
        const addressRange = `${item.startAddress}-${item.endAddress}`

        if (addressRanges.has(addressRange)) {
            addressRanges.set(addressRange, addressRanges.get(addressRange) + 1)
        } else {
            addressRanges.set(addressRange, 1)
        }
    }

    const duplicateRanges = []

    for (const [ range, count ] of addressRanges) {
        if (count > 1) {
            duplicateRanges.push(range)
        }
    }

    return duplicateRanges
}

问题分析 #

原代码的核心问题是通过字符串拼接的方式判断范围是否重复，这种方式只能识别完全一致的范围，无法处理部分重叠、包含等情况。要解决这个问题，需要基于数值范围的逻辑来判断重叠关系。

解决方案 #

实现思路 #

1. 排序简化判断：先将所有地址范围按startAddress升序排序，这样每个范围只需要和前一个已遍历的范围对比，就能发现是否存在重叠，无需和所有历史范围逐一比较，提升效率。
2. 重叠判断逻辑：对于两个已排序的范围[prevStart, prevEnd]和[currStart, currEnd]，只要currStart <= prevEnd，就说明两个范围存在重叠或完全包含的情况。

完整代码 #

const findInvalidRanges = (data) => {
    // 复制原数组并按起始地址升序排序，避免修改原数据
    const sortedRanges = [...data].sort((a, b) => a.startAddress - b.startAddress);
    const invalidPairs = [];

    for (let i = 1; i < sortedRanges.length; i++) {
        const current = sortedRanges[i];
        const previous = sortedRanges[i - 1];

        // 判断当前范围是否与前一个范围重叠或重复
        if (current.startAddress <= previous.endAddress) {
            invalidPairs.push({
                conflictingId: current.id,
                conflictingRange: `${current.startAddress}-${current.endAddress}`,
                overlapsWithId: previous.id,
                overlapsWithRange: `${previous.startAddress}-${previous.endAddress}`
            });
        }
    }

    return invalidPairs;
}

代码说明 #

• 排序处理：使用扩展运算符复制原数组后再排序，避免修改输入的原始数据。
• 重叠判断：利用排序后的特性，只需要对比当前范围的起始地址和前一个范围的结束地址，就能快速判断是否重叠。
• 返回结果：返回包含冲突范围详细信息的数组，方便定位具体是哪两个范围存在问题，便于后续处理。

测试验证 #

用示例数据测试：

const testData = [
    { id: 23, startAddress: 10, endAddress: 15 },
    { id: 24, startAddress: 11, endAddress: 13 },
    { id: 25, startAddress: 21, endAddress: 23 }
];

console.log(findInvalidRanges(testData));
// 输出结果：
// [
//   {
//     conflictingId: 24,
//     conflictingRange: '11-13',
//     overlapsWithId: 23,
//     overlapsWithRange: '10-15'
//   }
// ]

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