使用Stack<pair<int,int>>合并重叠区间时的入栈错误问题

我正在合并如下重叠区间：

5 12, 1 8, 14 19, 22 28, 25 27, 27 30

我采用pair<int, int>模板的逻辑，但无法将pair元素推入Stack<pair<int, int>>，因为我传入的是(&int, &int)而非(int, int)，请问该如何解决？

附上我的代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

void mergeOverlappingIntervals(vector<vector<int>> &arr) {
    vector<pair<int, int>> v;
    for(int i=0; i<arr.size(); i++) {
        v.push_back(make_pair(arr[i][0], arr[i][1]));
    }
    sort(v.begin(), v.end());
    // for(auto x:v) {
    //     cout << x.first << " " << x.second << endl;
    // }
    stack<pair<int, int>> st;
    st.push(v[0].first, v[0].second);
    for(int i=1; i<v.size(); i++) {
        int top = st.top();
        if(v[i].first <= top.second) {
            top.second = max(top.second, v[i].second);
        }
        st.push(v[i].first, v[i].second);
    }
    while(!st.empty()) {
        int top = st.top();
        cout << top.fist << " " << top.second << endl;
        st.pop();
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> arr(n, vector<int>(2, 0));
    for(int i=0; i<n; i++) {
        cin >> arr[i][0];
        cin >> arr[i][1];
    }
    mergeOverlappingIntervals(arr);
    return 0;
}

你的代码存在几处关键错误，导致无法正确将pair推入栈，以下是具体修正方案：

1. 栈push方法的参数错误 #

stack<pair<int, int>>的push()函数仅接受一个pair<int, int>类型参数，不能直接传入两个int值。你可以直接传入vector中已有的pair对象，或者用make_pair构造新pair：

• 错误写法：st.push(v[0].first, v[0].second);
• 正确写法：st.push(v[0]); 或 st.push(make_pair(v[0].first, v[0].second));

同理，循环内的st.push(v[i].first, v[i].second);也要改成st.push(v[i]);（后续还需调整该部分逻辑）。

2. 栈顶元素的类型声明错误 #

st.top()返回的是pair<int, int>&类型引用，不能赋值给int类型变量。需将top声明为pair<int, int>&，这样才能修改栈顶元素的区间范围：

• 错误写法：int top = st.top();
• 正确写法：pair<int, int>& top = st.top();

3. 合并区间的逻辑错误 #

当前代码不管区间是否重叠都会将当前区间推入栈，导致合并失败。正确逻辑是：若当前区间与栈顶区间重叠，就更新栈顶区间的右边界；若不重叠，再将当前区间推入栈。修改后的循环代码如下：

for(int i=1; i<v.size(); i++) {
    pair<int, int>& top = st.top();
    if(v[i].first <= top.second) {
        // 重叠时更新栈顶区间的右边界为较大值
        top.second = max(top.second, v[i].second);
    } else {
        // 不重叠时推入当前区间
        st.push(v[i]);
    }
}

4. 拼写错误 #

输出语句中的top.fist是拼写错误，应改为top.first。

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

void mergeOverlappingIntervals(vector<vector<int>> &arr) {
    vector<pair<int, int>> v;
    for(int i=0; i<arr.size(); i++) {
        v.push_back(make_pair(arr[i][0], arr[i][1]));
    }
    sort(v.begin(), v.end());
    
    stack<pair<int, int>> st;
    st.push(v[0]);
    
    for(int i=1; i<v.size(); i++) {
        pair<int, int>& top = st.top();
        if(v[i].first <= top.second) {
            top.second = max(top.second, v[i].second);
        } else {
            st.push(v[i]);
        }
    }
    
    // 栈是后进先出结构，直接输出会得到逆序区间，转存到vector反转后输出可保证顺序正确
    vector<pair<int, int>> result;
    while(!st.empty()) {
        result.push_back(st.top());
        st.pop();
    }
    reverse(result.begin(), result.end());
    
    for(auto &interval : result) {
        cout << interval.first << " " << interval.second << endl;
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> arr(n, vector<int>(2, 0));
    for(int i=0; i<n; i++) {
        cin >> arr[i][0];
        cin >> arr[i][1];
    }
    mergeOverlappingIntervals(arr);
    return 0;
}

额外说明：栈的特性是后进先出，直接输出栈内元素会得到逆序的合并区间，因此修正后的代码先将栈内元素转移到vector，反转后再输出，保证区间顺序从小到大排列。

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