给定起点距离和终点距离对,如果两个停靠站有重叠,则减少公交车数量。例如:
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;
}
3条答案
按热度按时间vnzz0bqm1#
您的错误位于
if(y.second >= st.top().first)
。如果st
在此处为空,该怎么办?只要将
if(st.size() > 0)
移到外面,您的代码就会正常运行。q5iwbnjs2#
您正在空堆栈上呼叫top。
在进入while循环体之前,你要检查栈是否为空。所以考虑一下栈只有一个元素的情况,while循环检查通过,你进入了while循环体。调用pop一次,你的栈现在是空的。然后你调用top,它本质上是在一个空栈上。
h79rfbju3#