C++实现区间合并时输出随机长整数问题排查

问题描述 #

程序目标是合并所有存在重叠或相邻关系的扇区区间，最终计算合并后最大区间的长度，但运行时输出不稳定，偶发输出1550870207这类无意义随机长整数，无法稳定得到预期结果。

问题代码 #

#include <cstdio>
using namespace std;

int main() {
freopen("beachin.txt", "r", stdin);
freopen("beachout.txt", "w", stdout);

int n, u, k, x;
scanf("%d %d %d %d", &n, &u, &k, &x);
int umbrellas[u][2];
for (int i = 0; i < u; i++) {
    scanf("%d %d", &umbrellas[i][0], &umbrellas[i][1]);
}

int groups[u][2];
int len = 0;
for (int i = 0; i < u; i++) {
    int s1 = umbrellas[i][0];
    int e1 = umbrellas[i][1];
    int found = false;
    for (int a = 0; a < len; a++) {
        int s2 = groups[a][0];
        int e2 = groups[a][1];
        if ((s1 <= e2 && s1 >= s2) || (e1 >= s2 && e1 <= e2) || (s1 <= s2 && e1 >= e2)) {
            int start, end;
            if (s1 < s2) start = s1;
            else start = s2;
            if (e1 > e2) end = e1;
            else end = e2;
            groups[a][0] = start;
            groups[a][1] = end;
            found = true;
        }
    }
    if (found == false) {
        len++;
        groups[len][0] = s1;
        groups[len][1] = e1;
    }
}

int largest = 0;
for (int i = 0; i < len; i++) {
    int current = groups[i][1]-groups[i][0]+1;
    if (current >= largest) largest = current;
}


printf("%d\n", largest);
return 0;
}

测试用例 #

输入内容：

7 2 5 2
4 5
5 6

预期输出：2
实际表现：偶发输出正确值2，多数时候输出随机超大整数。 #

根因分析 #

核心问题是数组下标越界写入，触发C++未定义行为，问题出在新增分组的代码段：

if (found == false) {
    len++;
    groups[len][0] = s1;
    groups[len][1] = e1;
}

初始len值为0，代表当前groups数组中有效分组数量为0。当第一个未匹配到已有分组的区间需要存入时，代码先执行len++把len从0变成1，随后写入groups[1]的位置，但C++数组有效下标是从0开始计数的，第一个空位置本应该是groups[0]。
这就导致：

• groups[0]的内存空间始终没有被写入有效值，保留着栈上分配时的随机脏数据
• 后续计算最大长度的循环从i=0开始遍历，读取到groups[0]里的随机脏值做计算，就会得到随机的超大整数
• 偶发输出正确值的情况，是刚好groups[0]位置的脏数据计算出的长度小于正确分组的长度，才会碰巧输出正确结果

修复方案 #

把新增分组的逻辑调整为先写入对应下标，再更新len值即可修复当前的随机输出问题：

if (found == false) {
    groups[len][0] = s1;
    groups[len][1] = e1;
    len++;
}

额外提示：当前代码的区间重叠判断逻辑存在其他缺陷：当新区间覆盖多个已有分组时，无法合并多个重叠分组，且相邻区间（比如一个区间结束于5，下一个开始于6）的判断条件也未覆盖，会导致区间合并结果错误，建议后续补充调整。

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