At first I struggled with the Big O(n^2) solution but for some reason, the Big O(n log(n)) solution - sorting cost - resonated with me.

The key is to sort via the start of the interval;

then you simply check to see if the end of the current interval is greater than the start of the next interval:

- If it is not, add it it to the output
- If it is, merge by assigning the min start and the max end;

```
vector<Interval> merge(vector<Interval>& intervals) {
if(intervals.size() == 0) {
return intervals;
}
//Key to the solution
sort(intervals.begin(), intervals.end(), [] (Interval a, Interval b) {
return a.start < b.start;
});
int i = 0;
int j = 1;
vector<Interval> result;
result.push_back(intervals[0]);
while(j < intervals.size()) {
//check for overlap
if(result[i].end >= intervals[j].start) {
result[i].start = min(result[i].start, intervals[j].start);
result[i].end = max(result[i].end, intervals[j].end);
j++;
} else {
result.push_back(intervals[j]);
i++; j++;
}
}
return result;
}
```