#include<bits/stdc++.h>
using namespace std;
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};
vector<Interval> insertt(vector<Interval> &intervals, Interval newInterval)
{
int n=intervals.size(),leftfound=0,rightfound=0,count=0;
if(n==0)//for the case when intervals vector is empty
{ intervals.push_back(newInterval);
return intervals;}
int t=0;
if(newInterval.end<newInterval.start)//if(start>end) swap
{
t=newInterval.start;
newInterval.start=newInterval.end;
newInterval.end=t;
}
if(newInterval.start>intervals[n-1].end)//if the newInterval succedes every other
{
intervals.insert(intervals.end(),newInterval);
return intervals;
}
if(newInterval.end<intervals[0].start)//if the newInterval is precedes every other
{
intervals.insert(intervals.begin(),newInterval);
return intervals;
}
auto left=intervals.begin(),right=intervals.begin(); //just initialising with something
auto it=intervals.begin() ; // iterator for loops
while((*it).start<newInterval.start&&it!=intervals.end()) //*it is dereferencing the iterator to
{ //get the element of vector "intervals" at that index
it++;}
it--; // decrementing it to reach the desired interval
if((*it).start<=newInterval.start&&(*it).end>=newInterval.start)
{leftfound=1;left=it;}
else left=it+1;
it=left;
while((*it).end<newInterval.end&&it!=intervals.end())
it++;
if((*it).start<=newInterval.end&&(*it).end>=newInterval.end)
{ rightfound=1; right=it;
}
else right=it-1;
if(right-left==-1&&leftfound==0&&rightfound==0)// this if will be true in cases like:
intervals.insert(left,newInterval); //intervals=[(1,2),(8,10)] and newInterval=(4,6)
else //in every other case this else will execute
{
if(leftfound==0)
(*left).start=newInterval.start;
if(rightfound==0)
(*left).end=newInterval.end;
else (*left).end=(*right).end;
//count=right-left;
}
left=left+1;
//while(count--)
//cout<<"current left pe value hai : ("<<left->start<<", "<<left->end<<")"<<endl;
//cout<<"current right pe value hai : ("<<right->start<<", "<<right->end<<")"<<endl;
intervals.erase(left,right+1);
return intervals;
}
int main()
{
Interval arr[]={Interval(3,5),Interval(8,10)};
Interval ni(1,12);
vector<Interval> intervals(arr,arr+sizeof(arr) / sizeof(arr[0]));
insertt(intervals,ni);
/*
auto it=intervals.begin();
for(auto it:intervals);
cout<<it->start<<" "<<it->end;*/
for (int i = 0; i < intervals.size(); i++)
cout<<intervals[i].start<<" "<<intervals[i].end<<" ";
return 0;
}