Efficient c++ solution using Multimap


#1
for(int i =0;i<n;i++){
    if(A[i].start>A[i].end)swap(A[i].start,A[i].end);
}
multimap<int,int> m;													//for sorting the intervals
for(int i =0;i<n;i++){
    m.insert({A[i].start,A[i].end});
}

vector<Interval> AB(n);
multimap<int,int> :: iterator itr;							//we can not acces the map element like m.first or m.second  it is only valid in pairs

int j = 0;
for(itr = m.begin();itr!=m.end();++itr){
AB[j] = {itr->first,itr->second};
j++;
}

int pos = -1;
Interval ans = AB[0];
vector<Interval> a;

for(int i = 0;i<n-1;i++){
    if(max(ans.start,AB[i+1].start)<=min(ans.end,AB[i+1].end)){//overlap
        ans = {min(ans.start,AB[i+1].start),max(ans.end,AB[i+1].end)};
    }
    else{
        a.push_back(ans);
        ans = AB[i+1];
    }
}
a.push_back(ans);//merging last answer

return a;

}