Best Optimal Solution - C++

google
Tags: #<Tag:0x00007f242590a6a0>

#1
/**
  • Definition for an interval.
  • struct Interval {
  • int start;
    
  • int end;
    
  • Interval() : start(0), end(0) {}
    
  • Interval(int s, int e) : start(s), end(e) {}
    
  • };
    */
    bool cmp(Interval a,Interval b){
    return (a.start<b.start);
    }

vector Solution::merge(vector &A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
int n=A.size();
vector ans;
if(n==0) return ans;

sort(A.begin(),A.end(),cmp);
Interval temp=A[0];
for(auto it:A){
    if(temp.end>=it.start){
            temp.end=max(temp.end,it.end);
        }
        else{
            ans.push_back(temp);
            temp=it;
        }
    }
ans.push_back(temp);
return ans;

}