You need to enable JavaScript to run this app. 合并重叠区间代码对负数值区间处理失效的问题排查与修复
优惠活动
大模型
产品
解决方案
定价
更多

合并重叠区间代码对负数值区间处理失效的问题排查与修复

现有代码缺陷定位

1. 输入区间无合法性校验,负数值场景下区间定义颠倒

用于正测试的输入区间都满足lo < hi的合法区间定义(左端点值小于右端点值,表示从较小数到较大数的连续范围),但替换为负数值输入时,直接将原有正区间的端点加负号输入,没有调整端点顺序,导致所有输入的区间都出现lo > hi的反向错误:

  • 比如输入的-2 -4对应结构体里lo=-2, hi=-4,实际如果是数轴上从-4到-2的范围,正确的合法区间应该是lo=-4, hi=-2,当前写法完全把区间方向搞反,后续所有基于区间大小的判断逻辑都会失效。
  • 这种反向区间会直接导致栈顶存储的hi值比lo值还小,比如压入栈的第一个排序后的区间是lo=-10, hi=-12,此时hi=-12 < lo=-10,所有后续区间的左端点判断都会因为值的大小关系完全不满足条件,直接触发压栈逻辑,没有任何合并效果。

2. 重叠判断条件过于严苛,存在场景覆盖漏洞

当前写的重叠判断逻辑是:

if (vectorIntervale[i].lo > stivaIntervale.top().lo && vectorIntervale[i].lo < stivaIntervale.top().hi)

这个条件存在三个明显问题:

  • 多余判断:因为已经按lo升序完成排序,后续遍历的所有区间的lo一定大于等于栈顶区间的lo,vectorIntervale[i].lo > stivaIntervale.top().lo这个判断是冗余的,还会漏掉左端点和栈顶区间左端点相等的合并场景。
  • 严格边界判断错误:条件里用的是<严格小于,漏掉了当前区间左端点等于栈顶区间右端点的相邻可合并场景。
  • 逻辑不通用:该判断仅在栈顶区间是合法正向区间(lo < hi)时成立,一旦区间颠倒,不等式的大小关系会完全反转。
    通用的、适用于任意正向合法区间的重叠判断(排序后场景)为:只要当前区间的左端点小于等于栈顶区间的右端点,就说明两个区间存在重叠/相邻,可以合并。
修复方案

步骤1:修正区间读入逻辑,保证区间合法性

在Interval的读入函数里,自动将读入的两个端点做大小交换,保证lo存较小值,hi存较大值:

void Interval::citire()
{
    int x, y;
    std::cin >> x >> y;
    lo = std::min(x, y);
    hi = std::max(x, y);
}

这个调整可以兼容任意输入顺序,不管用户输入的两个值谁大谁小,都能生成正确的数轴区间,不会出现反向定义的问题。

步骤2:替换正确的重叠判断逻辑

把原有的严苛判断替换为通用的重叠条件,同时合并时正确取右端点的最大值:

void determinareReuniune(int n, Interval vectorIntervale[])
{
    std::sort(vectorIntervale, vectorIntervale + n, functieComparareIntervalCrescator);
    std::stack<Interval> stivaIntervale;
    stivaIntervale.push(vectorIntervale[0]);
    for (int i = 1; i < n; i++)
    {
        Interval& top = stivaIntervale.top();
        // 通用重叠判断:当前左端点 <= 栈顶右端点,即可合并
        if (vectorIntervale[i].lo <= top.hi)
        {
            // 更新栈顶右端点为两者的最大值
            top.hi = std::max(top.hi, vectorIntervale[i].hi);
        }
        else
        {
            stivaIntervale.push(vectorIntervale[i]);
        }
    }
    afisareStack(stivaIntervale);
}

修复完成后,你用于测试的负输入会输出正确的合并结果:-4 -1、-9 -5、-12 -10,和正数值测试的合并逻辑完全一致,负数本身不会影响算法判断。

关于照搬参考教程也出问题的原因

参考教程的示例代码默认输入的所有区间都是合法正向区间(lo <= hi),没有做端点合法性校验,如果输入的是颠倒的反向区间,任何正确的合并算法都无法得到预期结果——因为输入本身就不符合区间的基本定义。出现问题的本质不是算法不支持负数,而是负数值输入时没有保证区间的合法结构,加上判断条件写得太严格,共同导致了合并逻辑完全失效。


内容的提问来源于stack exchange,提问作者user14399919

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.13 19:36:04