C++ Linear Time


#1

bool compareInterval(Interval a,Interval b){
return (a.start<b.start);
}
vector Solution::merge(vector &A) {
vector res;

int n = A.size();
sort(A.begin(),A.end(),compareInterval);
res.push_back(A[0]);
for(int i=1;i<n;i++){
    Interval top = res.back();
    if(top.end<A[i].start)
      res.push_back(A[i]);
    else if(top.end<A[i].end){
        top.end = A[i].end;
        res.pop_back();
        res.push_back(top);
    }
}
return res;

}


#2

It is not a liner time solution as you are sorting the array which takes O(n*log(n)) time