c++ - 减少从一个城市到不同停靠点的公交车的重叠计数，我目前的方法可以优化吗？

Question

给定一对起始距离和结束距离，如果两个停靠点重叠，则减少公交车数量。例如:

input n=4
{2,8},{6,10},{12,14},{12,20}
output:2
explanation:route {2,8} and {6,10} overlap so it can be reduced to 1 route as {2,10}
similarly route {12,14} and {12,20} overlap it can be merged to 1.

input n=4
{1,3} ,{7,9}, {4,6},{10,13}
output=4 since there is no overlapping

我的方法:我尝试对 vector<pair<int,int>> 进行排序按降序，插入stack<pair<int,int>>并使用了计数器count计算唯一路由并弹出堆栈检查条件，直到它变空。 尽管我的代码对我来说是 100% 正确的，但是当路由中没有重叠时它不会输出任何内容。，例如对于输入 n=4 , 路线: {1,3} ,{7,9}, {4,6},{10,13}它不输出任何东西。寻求帮助来解决此类问题。

#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]);
    }
    //looking for help from here ,basically i dont understands why my code in stack fails
    int count=0;
    while (!st.empty()){
        pair<int,int>y=st.top();
        st.pop();
        count++;
        if(y.second>=st.top().first){
            if(st.size()>0){
                 st.pop();
            }
        }

    }
    cout<<count;
}

Answer 1

您的错误在 if(y.second >= st.top().first)。如果这里的 st 是空的呢？

#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<int(v.size());i++){
        st.push(v[i]);
    }
    //looking for help from here ,basically i dont understands why my code in stack fails
    int count=0;
    while (!st.empty()){
        pair<int,int>y=st.top();
        st.pop();
        count++;
        if(st.size()>0){
            if(y.second>=st.top().first){
                st.pop();
            }
        }
    }
    cout<<count<<'\n';
}

只需将 if(st.size() > 0) 移到外面，您的代码就会正常运行。