合并重叠区间代码对负数值区间处理失效的问题排查与修复
现有代码缺陷定位
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
相关产品推荐
相关产品推荐

