合并重叠公交线路问题及C++栈实现无重叠场景错误排查

安全阿岳

2026-10-7

公交区间合并代码问题修复

错误原因

原代码存在两个核心问题：

未做栈空校验就访问st.top()：当栈中只剩最后1个元素，弹出后栈为空，此时执行st.top().first会触发段错误，程序直接终止，导致无输出。
区间合并逻辑不完整：直接弹出重叠区间后未将合并后的新区间压回栈，无法处理连续多个重叠的区间场景。

修正后的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
bool compare(pair<int,int>p1,pair<int,int>p2){
    return p1.first>p2.first;
}
int main(){
    int n;cin>>n;
    vector<pair<int,int>>v;
    for(int i=0;i<n;i++){
        int u,w;
        cin>>u>>w;
        v.push_back(make_pair(u,w));
    }
    sort(v.begin(),v.end(),compare);
    stack<pair<int,int>>st;
    for(int i=0;i<v.size();i++){
        st.push(v[i]);
    }
    int count=0;
    while (!st.empty()){
        pair<int,int> current = st.top();
        st.pop();
        // 循环合并所有和当前区间重叠的后续区间
        while(!st.empty() && current.second >= st.top().first){
            current.second = max(current.second, st.top().second);
            st.pop();
        }
        count++;
    }
    cout<<count;
    return 0;
}