Merge Intervals -- Leetcode

[Question]
Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

[Analysis]

If all intervals are sorted by their start points, the overlapping between two consecutive intervals A and B is simple: A.end > B.start. If B.start> A.end, B and the following intervals have no overlapping with A. Therefore, sort the intervals first, then scan the sorted interval list and merge them one by one when possible. The time complexity is O(N x log N + N).

Without sorting, the overlapping cases among intervals are complicated. It can not be done by one pass.

[Solution]
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool intersected( const Interval& a, const Interval& b) {
        return !(a.start>b.end || b.start>a.end);
    }
 
    vector<Interval> merge(vector<Interval> &intervals) {
        if (intervals.empty()) return intervals;
       
        sort(intervals.begin(), intervals.end(),
            [](Interval a, Interval b) { return a.start < b.start; }
        );
       
        int size = intervals.size();
        Interval temp (intervals[0].start, intervals[0].end);
        for (int i=1; i<size; i++) {
            if ( intersected(intervals[i], temp) ){
                temp.start = min(intervals[i].start, temp.start);
                temp.end = max(intervals[i].end, temp.end);
            }
            else {
                intervals.push_back(temp);
                temp = intervals[i];
            }
        }
        intervals.push_back(temp);
        intervals.erase(intervals.begin(), intervals.begin()+size);
        return intervals;
    }
};