Here’s the link to the problem:
I have tried to solve this problem but it gives WA on one test case(out of 6). Can you please tell me why its wrong. Please look into it and help me. Thanks in advance. Here’s my code:
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define debug(x) #x<<": "<<x<<" "
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll test;
cin>>test;
while(test>0)
{
ll n;
cin>>n;
vector<pair<ll,ll>> arr(n+1);
for(ll i = 0;i<n;i++)
{
ll a,b;
cin>>a>>b;
arr[i] = make_pair(b,a);
}
sort(arr.begin(),arr.end());
ll res = 1;
ll currentTime = arr[0].second+1;
for(int i = 1;i<n;i++)
{
ll startTime = arr[i].second;
ll endTime = arr[i].first;
// cout<<debug(currentTime)<<debug(endTime)<<debug(startTime)<<endl;
if(currentTime<=endTime)
{
res++;
currentTime = max(startTime+1,currentTime+1);
}
}
cout<<res<<endl;
test--;
}
}
I have been able to solve this problem using a set(below) but I can’t find what’s wrong in the above approach.
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define debug(x) #x<<": "<<x<<" "
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll test;//test cases
cin>>test;
while(test>0)
{
ll n;
cin>>n;
vector<pair<ll,ll>> arr(n);
set<ll> st;
for(ll i=0;i<n;++i)
{
ll s,e;
cin>>s>>e;
arr[i] = make_pair(e,s);
st.insert(s);
}
sort(arr.begin(),arr.end());
ll res=0;
for(ll i=0;i<n;++i)
{
ll startTime=arr[i].second;
ll endTime=arr[i].first;
auto it = st.lower_bound(startTime);
if(it!=st.end())
{
ll leastAvailable = *it;
if(leastAvailable>=startTime && leastAvailable<=endTime)
{
res++;
st.erase(it);
st.insert(leastAvailable+1);
}
}
}
cout<<res<<endl;
test--;
}
}
