InterviewBit合并区间题C++向量实现提交报错求助

看起来你的代码逻辑整体是对的，但提交时出现的free()错误，大概率是因为迭代器越界解引用导致的未定义行为——这种错误在本地测试时可能因为内存布局的巧合没有暴露，但在OJ平台的严格环境下会触发内存错误。

核心问题定位 #

你的代码中有两处风险点，都会导致解引用end()迭代器（指向vector末尾之后的非法位置）：

1. 循环条件顺序错误：
   在查找left和right的循环中，你先判断了元素的属性（比如(*it).start < newInterval.start），再判断it != intervals.end()。当迭代器走到end()时，先解引用它会直接访问非法内存，触发未定义行为。

2. 未检查迭代器有效性就解引用：
   在查找right的最后一步，当newInterval.end大于所有区间的end时，循环会让it走到end()，此时你直接解引用(*it)来判断重叠，同样会访问非法内存。

代码修复方案 #

针对这两个问题，我们可以对代码进行以下调整：

1. 修正循环条件的顺序

把it != intervals.end()放在循环条件的最前面，确保只有迭代器有效时才会解引用元素：

// 查找left的循环修改
while(it != intervals.end() && (*it).start < newInterval.start)
    it++;

// 查找right的循环修改
while(it != intervals.end() && (*it).end < newInterval.end)
    it++;

2. 检查迭代器有效性再判断rightfound

在判断right是否与newInterval重叠前，先确认it不是end()，避免非法解引用：

// 替换原来的right判断逻辑
rightfound = 0;
if(it != intervals.end()) {
    if((*it).start <= newInterval.end) {
        rightfound = 1;
        right = it;
    } else {
        right = it - 1;
    }
} else {
    // it是end()，说明newInterval.end大于所有区间的end
    right = intervals.end() - 1;
}

完整修复后的代码片段

整合修改后的关键部分代码如下：

vector<Interval> Solution::insert(vector<Interval> &intervals, Interval newInterval) {
    int n=intervals.size(),leftfound=0,rightfound=0,count=0;
    if(n==0) //for the case when intervals vector is empty
    {
        intervals.push_back(newInterval);
        return intervals;
    }
    int t=0;
    if(newInterval.end<newInterval.start) //if(start>end) swap
    {
        t=newInterval.start;
        newInterval.start=newInterval.end;
        newInterval.end=t;
    }
    if(newInterval.start>intervals[n-1].end) //if the newInterval succedes every other
    {
        intervals.insert(intervals.end(),newInterval);
        return intervals;
    }
    if(newInterval.end<intervals[0].start)//if the newInterval precedes every other element
    {
        intervals.insert(intervals.begin(),newInterval);
        return intervals;
    }
    auto left=intervals.begin(),right=intervals.begin(); //just initialising with something
    auto it=intervals.begin() ; // iterator for loops
    // 修正后的left查找循环
    while(it != intervals.end() && (*it).start < newInterval.start)
        it++; //get the element of vector "intervals" at that index
    it--; // decrementing it to reach the desired interval
    if((*it).start<=newInterval.start&&(*it).end>=newInterval.start)
    {
        leftfound=1;left=it;
    }
    else
        left=it+1;
    it=left;
    // 修正后的right查找循环
    while(it != intervals.end() && (*it).end < newInterval.end)
        it++;
    // 修正后的right判断逻辑
    rightfound = 0;
    if(it != intervals.end()) {
        if((*it).start <= newInterval.end) {
            rightfound = 1;
            right = it;
        } else {
            right = it - 1;
        }
    } else {
        right = intervals.end() - 1;
    }
    if(right-left==-1&&leftfound==0&&rightfound==0)// this if will be true in cases like:
        intervals.insert(left,newInterval); //intervals=[(1,2),(8,10)] and newInterval=(4,6)
    else //in every other case this else will execute
    {
        if(leftfound==0)
            (*left).start=newInterval.start;
        if(rightfound==0)
            (*left).end=newInterval.end;
        else
            (*left).end=(*right).end;
    }
    left=left+1;
    intervals.erase(left,right+1);
    return intervals;
}

为什么这样修复？ #

• 循环条件调整后，只有当迭代器有效时才会访问元素，避免了非法内存访问。
• 对right的判断增加了迭代器有效性检查，当it走到end()时，我们直接将right指向最后一个有效元素，确保后续的erase操作不会使用非法迭代器。

这样修改后，代码就能避免触发free()相关的内存错误，顺利通过平台的提交检测了。

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