leetcode Question 51: Merge Intervals

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

Analysis:

To check the intersections between interval [a,b] and [c,d],  there are four cases (equal not shown in the figures):

    a____b

c____d

a____b

     c____d

a_______b

    c___d

   a___b

c_______d

But we can simplify these into 2 cases when check the smaller (smaller start point) interval with the bigger interval.

For the problem, the idea is simple. First sort the vector according to the start value. Second, scan every interval, if it can be merged to the previous one, then merge them, else push it into the result vector.

Note here:
The use of std::sort to sort the vector, need to define a compare function, which need to be static. (static bool myfunc() ) The sort command should be like this:  std::sort(intervals.begin,intervals.end, Solution::myfunc); otherwise, it won't work properly.

If using python, the sort function is much easier with the lambda func.

Code (C++):

/**
 * 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 myfunc(const Interval &a, const Interval &b){
        return (a.start < b.start);
    }
    vector<Interval> merge(vector<Interval> &intervals) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<Interval> res;
        if (intervals.size()==0){return res;}
        std::sort(intervals.begin(),intervals.end(),Solution::myfunc);
        res.push_back(intervals[0]);
        for (int i=1;i<intervals.size();i++){
            if (res.back().end>=intervals[i].start){
                res.back().end=max(res.back().end,intervals[i].end);
            }else{
                res.push_back(intervals[i]);
            }   
        }
        return res;
    }
};

Code(Python):

# Definition for an interval.

# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    # @param intervals, a list of Interval
    # @return a list of Interval
    def merge(self, intervals):
        res = []    # result list
        
        if len(intervals)==0:
            return res
        
        #sort list according to the start value    
        intervals.sort(key=lambda x:x.start)
        
        res.append(intervals[0])
        
        #scan the list
        for i in xrange(1,len(intervals)):
            cur = intervals[i]
            pre = res[-1]
            #check if current interval intersects with previous one
            if cur.start <= pre.end:
                res[-1].end = max(pre.end, cur.end) #merge
            else:
                res.append(cur) #insert
                
        return res