c++ 减少从一个城市到不同站点直线运行的公共汽车的重叠计数数量,我目前的方法是否可以优化?

o2g1uqev  于 2022-12-01  发布在  其他
关注(0)|答案(3)|浏览(96)

给定起点距离和终点距离对,如果两个停靠站有重叠,则减少公交车数量。例如:

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;
}
vnzz0bqm

vnzz0bqm1#

您的错误位于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)移到外面,您的代码就会正常运行。

q5iwbnjs

q5iwbnjs2#

您正在空堆栈上呼叫top。
在进入while循环体之前,你要检查栈是否为空。所以考虑一下栈只有一个元素的情况,while循环检查通过,你进入了while循环体。调用pop一次,你的栈现在是空的。然后你调用top,它本质上是在一个空栈上。

h79rfbju

h79rfbju3#

python code is here:
def mergeIntervals(intervals):
    intervals.sort()
    stack=[]
    stack.append(intervals[0])
    for i in intervals[1:]:
        if stack[-1][0] <= i[0] <= stack[-1][-1]:
            stack[-1][-1] = max(stack[-1][-1], i[-1])
        else:
            stack.append(i)

    print(len(stack))

n,m=map(int,input().split())
arr=[]
for _ in range(n):
    l=list(map(int,input().split()[:m]))
    arr.append(l)
mergeIntervals(arr)

相关问题