# Easy C++ Solution with Explanations (O(nlogn) time and O(n) space)

• The idea to solve this problem is to first sort the intervals according to their `start` field and then scan the intervals from head to tail and merge those that overlap.

For sorting the intervals according to their `start` field, we define a comparison function as follows.

``````static bool comp(Interval interval1, Interval interval2) {
return interval1.start < interval2.start;
}
``````

Then all the intervals are sorted in the ascending order of `start`. Now we define a current interval `cur` and initialize it to be `intervals[0]`. Then we scan from `intervals[1]` to `intervals[n - 1]`. If it overlaps with `cur`, merge them; otherwise, add `cur` to `res`, update `cur` to be `intervals[i]` and move on with the merging process.

There are two required subroutines in the above process: `isOverlap` to tell whether two intervals overlap and `mergeTwo` to merge two overlapping intervals.

For `isOverlap`, since the intervals are sorted in ascending order of `start`, we simply need to guarantee that `end` of the left (with smaller `start`) interval is not less than `start` of the right (with larger `start`) interval.

For `mergeTwo`, just take the minimum of `start` and maximum of `end` of the two overlapping intervals and return a new interval with these two values.

The complete code is as follows, which should be self-explanatory.

``````class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
vector<Interval> res;
if (intervals.empty()) return res;
sort(intervals.begin(), intervals.end(), comp);
Interval cur(intervals[0].start, intervals[0].end);
for (int i = 1, n = intervals.size(); i < n; i++) {
if (isOverlap(cur, intervals[i]))
cur = mergeTwo(cur, intervals[i]);
else {
res.push_back(cur);
cur = intervals[i];
}
}
res.push_back(cur);
return res;
}
private:
static bool comp(Interval interval1, Interval interval2) {
return interval1.start < interval2.start;
}
bool isOverlap(Interval interval1, Interval interval2) {
return interval1.end >= interval2.start;
}
Interval mergeTwo(Interval interval1, Interval interval2) {
int end = max(interval1.end, interval2.end);
return Interval(interval1.start, end);
}
};``````

• Actually, I think it's unnecessary to calculate start in mergeTwo(), since the start is ordered.

• Hi, Mark1013. Yeah, you're right. I have updated my code now. Thanks :-)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.