JavaScript合并重叠区间算法[1,4],[2,3]测试用例结果不符求解

你的核心逻辑缺陷是：重叠区间合并时，未对两个区间的结束值取最大值，直接将前序区间的结束值覆盖为当前区间的结束值，仅当前序区间的结束值小于当前区间结束值时才能得到正确结果，一旦当前区间是被前序区间完全包含的子区间，就会出现错误输出。

具体测试用例复现逻辑 #

第三个测试用例输入[[1,4],[2,3]]按区间左端点排序后顺序不变：

1. 初始前序区间为[1,4]，加入结果数组
2. 遍历到当前区间[2,3]，判定前序区间结束值4 >= 当前区间起始值2，判定为重叠
3. 你直接将前序区间的结束值修改为当前区间的结束值3，最终得到错误结果[[1,3]]
4. 正确逻辑应取两个结束值的最大值max(4,3)=4，合并后区间仍为[1,4]，与官方预期一致

前两个用例通过的原因 #

前两个测试用例中，后一个区间的结束值均大于前序区间的结束值，直接覆盖的操作刚好命中正确结果，属于巧合，不代表逻辑正确：

• 用例1中后序区间[2,6]的结束值6 > 前序区间结束值3，覆盖后结果正确
• 用例2中后序区间[4,5]的结束值5 > 前序区间结束值4，覆盖后结果正确

修正后的代码 #

var merge = function(intervals) {
    // 按区间左端点升序排序
    intervals.sort((a, b) => a[0] - b[0])
    
    let previous = intervals[0];
    let result = [previous];
    
    for(let i = 1; i < intervals.length; i++) {
        let current = intervals[i];
        if(previous[1] >= current[0]) {
            // 合并时取两个区间结束值的最大值
            previous[1] = Math.max(previous[1], current[1]);
        } else {
            result.push(current);
            previous = current;
        }
    }
    return result;
};

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