O(n) explanantion


#1

you just need to compare end and starting time
if end time is greater than start time then :
min(start, A[i+1].start)
max(end, A[i+1].end)
else
ans.push_back(start, end)

beneath is a simple cpp code of the following
int n = A.size();
vector ans;
sort(A.begin(),A.end(), compare);
int start = A[0].start, end = A[0].end;
int i =0;
for(i;i<n-1;i++){
if(end>=A[i+1].start){
start = min(start, A[i+1].start);
end = max(A[i+1].end, end);
}
else{
ans.push_back(Interval(start,end));
start = A[i+1].start;
end = A[i+1].end;

    }
}
ans.push_back(Interval(start,end));
return ans;

#2

This is not O(n) solution .