can anyone find out the error in my code ,its not passing one of the subset.
Corner Case : If a pair is present where Si = Ei, eg. {4,4} ; {5,5}.
Then just don’t consider the pair even while taking the input into a vector or set.
The reason is because , here the k value ranges from 0 to 1e9 . Hence , your worst time complexity is O(1e9) which is not possible to compute . Hence , a TLE.
Thanks for the time
For those who are wondering why to sort…
Take this test case for example:
1
3 3 10
2 5
3 6
1 9
If not sorted then the result will be “yes” but it should be “no”.
2 Likes
Just sort the intervals in increasing order on the basis of start time and then merge them.
from the list of interval obtained subtract the duration of each interval of the list from total minutes(F) and check if the F >= K for affirmation or negation.
Can anyone tell me at which testCase my Code is getting WA ??
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define time cerr<<"Time taken : " <<(float)clock()/CLOCKS_PER_SEC <<" secs"<<"\n" ;
#define F first
#define S second
#define pb push_back
typedef long long int ll ;
#define INF 1e15
#define MOD (int)1e9+0
ll GCD (ll a , ll b) {
if (b == 0) {
return a ;
}
return GCD(b , a % b) ;
}
ll LCM(ll a , ll b) {
return (a * b) / GCD(a , b) ;
}
void solve() {
ll n , k, f ;
cin >> n >> k >> f;
vector<pair<ll,ll>>vp ;
for(ll i=0 ; i < n ; i++){
ll a,b ;
cin >> a >> b ;
vp.pb({a,b}) ;
}
for(auto p: vp){
if(p.F == 0 && p.S == f){
cout <<"NO\n" ;
return ;
}
}
ll d2 = vp[0].F ;
if(d2 >= k){
cout << "YES\n" ;
return ;
}
ll d1 = f - vp[n-1].S ;
if(d1 >= k){
cout << "YES\n" ;
return ;
}
ll sum = 0 ;
for(ll i =1 ;i<n ;i++){
ll diff = vp[i].F - vp[i-1].S ;
// cout << diff <<"\n" ;
if(diff > 0){
sum+=diff ;
}
}
if(sum >= k){
cout <<"YES\n" ;
return ;
}
cout <<"NO\n" ;
}
int32_t main() {
fast ; time;
#ifndef ONLINE_JUDGE
freopen("input.txt" , "r" , stdin) ;
freopen("output.txt" , "w" , stdout) ;
#endif
ll t = 1;
cin >> t;
while (t--) {
solve() ;
}
return 0 ;
}Hey @nskybytskyi
I did consider the cases where more than one invigilators are monitoring, pls help me know where i went wrong 
//સહજ
//www.linkedin.com/in/sahaj-patel-2b0b3920b/
#define ll long long
#include iostream> // i did not keep < cause it didnt appear in blog
#include map>
#include vector>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T; cin>>T;
while(T--){
int n, k ,f;
cin>>n>>k>>f;
int s, e;
map<int, int> m;
for(int i=0; i<n; i++){
cin>>s>>e;
m[s] = e;
}
map<int, int> :: iterator it = m.begin();
int minist = it->first;
int maxilim = it->second;
int montime = 0;
it = m.begin();
it++;
for(; it!=m.end(); it++){
if(it->first < maxilim){
if(it->second <maxilim){
continue;
}
else if(it->second > maxilim){
maxilim = it->second;
}
}
else{
montime += maxilim - minist;
minist = it->first;
maxilim = it->second;
}
}
montime += maxilim - minist;
cout<<montime<<endl;
if(f-montime>=k) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
https://www.codechef.com/viewsolution/47096388
can someone please help me Only 3rd subtask is not passing…
hey i think you missed the case of multiple invigilator. if there is two invigilator in the time interval of 0 to 5 then 0 5 will be inputted twice in your pair and your code will add extra 5 minutes of invigilation. hope it will help.
I have tried all the test cases I could come up with but am still failing test case #1. I have read the editorial and my code seems to handle all three cases mentioned. Kindly help me figure out the issue. Thanks in advance!
Code 
Please provide some test where it will fail.
Replacable Code
while(x<n+2 && count<k)
{
if(flag)
{
prev=ar[x-1].e;
}
long cur=ar[x].s;
if(prev<cur)
{
if(flag==false)
{
flag=true;
continue;
}
count+=cur-prev;
}
else if(prev>cur)
{
flag=false;
}
// System.out.println(count);
x++;
}
Why don’t you replace this entire thing with one for loop?
Initialise a variable free_time with 0.
For each i, 1 \le i \le (N + 1), free_time += (ar[i].s - ar[i - 1].end).
You know the reason why I took 1 to N + 1.
Now, check if free_time >= k. Output YES or NO based on this condition.
Edit: This will not work unless you merge Overlapping Intervals.
I did the same thing in the last for loop used count as variable
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--)
{
int n, g, tg;
cin >> n >> g >> tg;
vector<pair<int, int>> a(n);
for(int i=0; i<n; i++)
cin >> a[i].first >> a[i].second;
int safe[tg];
memset(safe, 0, sizeof(safe));
for(int i=0; i<n; i++)
{
int s = a[i].first, e = a[i].second;
for(int j=s; j<e; j++)
safe[j] = 1;
}
int counter = 0;
for(int i=0; i<tg; i++)
{
if(safe[i] == 0)
counter++;
}
(counter >= g) ? cout << "yes\n" : cout << "no\n";
}
return 0;
}
can anyone help !!!
You haven’t told us what problem you’re running into, yet 
Yes they do take overlapping intervals