LeetCode: Merge Intervals

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].

---

We can sort the intervals by start points first and then traverse the list from start and merge neighbors if possible.

C++ Code:

/*
 * compare function for sorting Intervals
 */
bool comp_func(const Interval &x, const Interval &y){
    return x.start <= y.start;
}

/*
 * func: merge_interval
 * goal: merge all overlapping intervals
 * @param intervals: input interval vectors
 * return: interval set after merging
 */
/*
 * Sort the intervals by start points and iterate each interval
 * and merge them if possible
 * complexity: time O(nlogn), space O(1)
 */
vector<Interval> merge_interval(vector<Interval> &intervals){
    sort(intervals.begin(), intervals.end(), comp_func);
    vector<Interval> results;
    for(const auto& it : intervals){
        if(results.empty() || it.start > results.back().end){
            results.emplace_back(it);
        }
        else{
            auto &back = results.back();
            back.end = std::max(it.end, back.end);
        }
    }
    return results;
}

Python Code:

# func: merge overlapping intervals in the list
# @param intervals: a list of intervals
def merge_interval(intervals):
    intervals_sorted = sorted(intervals, lambda x, y: cmp(x.start, y.start))
    result = []
    for interval in intervals_sorted:
        if not result or result[-1].end < interval.start:
            result.append(interval)
        else:
            result[-1].end = max(result[-1].end, interval.end)
    return result