If all the interval don’t merges to single then it’s simple my output will be zero
else
for every interval I calculated the number of overlap it can have.
suppose overlap count for each index are
4 5 6 1 3 4 6 (might not be possible this type but suppose)
then if I see at index 3, this is connected to only one interval and if I delete that then this interval can be isolated from all the other ranges.
Or you can see by drawing a graph by supposing each interval as a vertex and overlap as a edge
Each vertex(Interval) has it edge(overlap) count
Edge count = total number of vertex it attached to = total number of edges adjacent to that vertex
this means if I have to isolated this graph into two disjoint parts,
then I will delete that edge count which is minimum in all of them.
What’s wrong in this??
#include<bits/stdc++.h>
#define mkp make_pair
#define MOD 1000000007
#define input(variable) scanf("%ld",&variable)
using namespace std;
typedef unordered_map<int,int> umap_int;
typedef vector vec;
int main() {
long int t;
input(t);
while(t–){
long int n;
input(n);
vec l;
vec r;
long int a,b;
vector<pair<long int,long int>> p;
for(int i=0;i<n;i++){
input(a);
input(b);
//Start of all
l.push_back(a);
// End of all
r.push_back(b);
p.push_back(mkp(a,b));
}
sort(l.begin(),l.end());
sort(r.begin(),r.end());
// count1 for keeping the overlapping interval for each index
vector<long int> count1;
long int tl,tr,pl,pr;
for(int i=0;i<n;i++){
tl=p[i].first;
tr=p[i].second;
//pl-(how many interval has their End equal or less than my current beginning
pl=lower_bound(r.begin(),r.end(),tl)-r.begin();
//pr-(how many interval has their beginning less than my current End)
pr=upper_bound(l.begin(),l.end(),tr)-l.begin();
//count1 tell me number of overlap my current interval can have.
count1.push_back((pr-pl-1));
}
long int ans = count1[0];
for(int i=1;i<n;i++)
ans=min(ans,count1[i]);
//ans is the minimum number of overlap
sort(p.begin(),p.end());
long int xx=p[0].second;
int full=1;
for(int i=1;i<n;i++){
if(xx>=p[i].first){xx=max(xx,p[i].second);}
else full=0;
}
//full will tell that all the range will merge to single or not
// if full is 0 that means they won't merge
// if full is 1 that I checked the minimum overlap I got should be less than n-1
//then my output will be my answer, else not possible (-1).
if(full==0)cout<<"0"<<endl;
else if(ans<(n-1)) cout<<to_string(ans)<<endl;
else cout<<"-1"<<endl;
}
return 0;
}
