acwing803区间合并问题

Question

acwing803区间合并问题，想不明白为什么遍历完整个seg之后还要特判一下
if(st!=-2e9) res.push_back({st,end})

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int>PII;
vector<PII>seg;
void merge(vector<PII>&seg){
    vector<PII> res;
    int st=-2e9,end=-2e9;
    for(auto item:seg){
        if(end<item.first){
            if(st!=-2e9) res.push_back({st,end});
            st=item.first;
            end=item.second; 
        }
        else end=max(end,item.second);
    }
    //处理最后一个段 ,这里不明白
    if(st!=-2e9) res.push_back({st,end});  
    seg=res;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;
        cin>>l>>r;
        seg.push_back({l,r}); 
    }
    merge(seg);
    cout<<seg.size()<<endl;
    return 0;
} 

Answer 1

引自免费微信小程序：皆我百晓生

好的，我很乐意帮助您解决这个问题。

首先，让我们分析一下这段代码的问题。代码试图实现一个merge函数，用于合并两个有序区间seg。这个函数的目标是将每个元素（根据其索引从0开始）放入结果序列 res 中。然而，在函数中，它在遍历整个seg后仍然特判了end，这导致某些输入可能不会被正确地合并到结果序列中。

接下来，我们提供一些改进方法：

1. 去掉特判：在找到结束点之前，直接访问end，从而跳过这部分检查。
2. 使用for循环迭代所有可能的结果，并根据当前end的位置来判断是否需要添加新元素。

以下是优化后的代码：

#include <iostream>
#include <vector>
#include <algorithm>

typedef pair<int, int> PII;

std::vector<PII> merge(std::vector<PII>& seg) {
    std::vector<PII> res;
    int start = -2e9, end = -2e9;
    for (const auto& item : seg) {
        if (start > item.first) {
            res.push_back({start, end});
            start = item.first;
            end = item.second;
        } else {
            end = std::max(end, item.second);
        }
    }

    if (start != -2e9) {
        res.push_back({start, end});
    }
    
    return res;
}

int main() {
    int n;
    std::cin >> n;

    for (int i = 0; i < n; ++i) {
        int l, r;
        std::cin >> l >> r;
        seg.push_back({l, r});

        if (l > r) {
            swap(l, r);
        }
    }

    std::vector<PII> res = merge(seg);

    std::cout << res.size() << '\n';
    return 0;
}

这段代码已经实现了以上改进，应该可以更准确地对merge函数进行操作。如果还有其他疑问，请随时告诉我。