fork download
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Interval {
  6. int start;
  7. int end;
  8. Interval() : start(0), end(0) {}
  9. Interval(int s, int e) : start(s), end(e) {}
  10. };
  11.  
  12. vector<Interval> insertt(vector<Interval> &intervals, Interval newInterval)
  13. {
  14.  
  15. int n=intervals.size(),leftfound=0,rightfound=0,count=0;
  16. if(n==0)//for the case when intervals vector is empty
  17. { intervals.push_back(newInterval);
  18. return intervals;}
  19.  
  20. int t=0;
  21. if(newInterval.end<newInterval.start)//if(start>end) swap
  22. {
  23. t=newInterval.start;
  24. newInterval.start=newInterval.end;
  25. newInterval.end=t;
  26. }
  27. if(newInterval.start>intervals[n-1].end)//if the newInterval succedes every other
  28. {
  29. intervals.insert(intervals.end(),newInterval);
  30. return intervals;
  31. }
  32. if(newInterval.end<intervals[0].start)//if the newInterval is precedes every other
  33. {
  34. intervals.insert(intervals.begin(),newInterval);
  35. return intervals;
  36. }
  37.  
  38. auto left=intervals.begin(),right=intervals.begin(); //just initialising with something
  39. auto it=intervals.begin() ; // iterator for loops
  40.  
  41. while((*it).start<newInterval.start&&it!=intervals.end()) //*it is dereferencing the iterator to
  42. { //get the element of vector "intervals" at that index
  43. it++;}
  44.  
  45. it--; // decrementing it to reach the desired interval
  46.  
  47. if((*it).start<=newInterval.start&&(*it).end>=newInterval.start)
  48. {leftfound=1;left=it;}
  49. else left=it+1;
  50.  
  51. it=left;
  52.  
  53. while((*it).end<newInterval.end&&it!=intervals.end())
  54. it++;
  55.  
  56. if((*it).start<=newInterval.end&&(*it).end>=newInterval.end)
  57. { rightfound=1; right=it;
  58. }
  59. else right=it-1;
  60.  
  61.  
  62. if(right-left==-1&&leftfound==0&&rightfound==0)// this if will be true in cases like:
  63. intervals.insert(left,newInterval); //intervals=[(1,2),(8,10)] and newInterval=(4,6)
  64.  
  65. else //in every other case this else will execute
  66. {
  67. if(leftfound==0)
  68. (*left).start=newInterval.start;
  69. if(rightfound==0)
  70. (*left).end=newInterval.end;
  71. else (*left).end=(*right).end;
  72. //count=right-left;
  73.  
  74. }
  75. left=left+1;
  76. //while(count--)
  77. //cout<<"current left pe value hai : ("<<left->start<<", "<<left->end<<")"<<endl;
  78. //cout<<"current right pe value hai : ("<<right->start<<", "<<right->end<<")"<<endl;
  79.  
  80. intervals.erase(left,right+1);
  81. return intervals;
  82. }
  83.  
  84. int main()
  85. {
  86. Interval arr[]={Interval(3,5),Interval(8,10)};
  87. Interval ni(1,12);
  88. vector<Interval> intervals(arr,arr+sizeof(arr) / sizeof(arr[0]));
  89. insertt(intervals,ni);
  90. /*
  91.   auto it=intervals.begin();
  92.   for(auto it:intervals);
  93.   cout<<it->start<<" "<<it->end;*/
  94. for (int i = 0; i < intervals.size(); i++)
  95. cout<<intervals[i].start<<" "<<intervals[i].end<<" ";
  96.  
  97. return 0;
  98. }
  99.  
  100.  
  101.  
  102.  
Success #stdin #stdout 0s 4380KB
stdin
Standard input is empty
stdout
1 12