[LeetCode] Merge Intervals

Problem Statement (link):

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:
The idea is simple, we keep comparing the end value of the previous interval with the start value of the current interval. If the end is smaller than the start, we push the previous interval into our result vector; otherwise, we merge the two intervals into one.

The time complexity is O(n).

Code:

/**
 * 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:
    static bool cmpFunc(Interval a, Interval b) {
        return a.start<b.start;
    }

    vector<Interval> merge(vector<Interval> &intervals) {
        if (intervals.size()<2) return intervals;
        std::sort(intervals.begin(), intervals.end(), cmpFunc);
        vector<Interval> res;
        int cur=1, prev=0;
        int start=intervals[prev].start, end=intervals[prev].end;
        while(cur<intervals.size()) {
            if (intervals[cur].start>end) {
                Interval *intv=new Interval(start, end);
                res.push_back(*intv);
                prev=cur;
                start=intervals[prev].start;
                end=intervals[prev].end;
                cur++;
            }
            else {
                end=max(end, intervals[cur].end);
                cur++;
            }
        }
        // push_back the rest
        Interval *intv=new Interval(start, end);
        res.push_back(*intv);
        return res;
    }
};