leetcode[55] 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].

这题主要会要知道如何对一个node型或者是struct进行排序。就是如何定义sort的比较函数，sort的比较函数本来默认的是小于函数，现在给定的struct类型没有定义的小于函数，所以要自己定义一个。根据左区间排序。

定义好后，进行排序，排好序后，扫面一次判断下一个的开头和前一个的结尾的大小，如果下一个开头大，那么前面一个就是分离的区间，记录答案。如果下一个的开头不比上一个的结尾大，那么就有重叠了，这时候就判断下一个的结尾是否比前一个的结尾大，大的话就替代它。所以我们要有一个指针指向保存了答案的vector的末尾，以便于和下一个开头判断。

/**
 * 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 {
private:
    static bool myCmp(Interval a, Interval b)
    {
        return a.start < b.start;
    }
public:
    vector<Interval> merge(vector<Interval> &intervals) 
    {
        if(intervals.empty()) return intervals;
        sort(intervals.begin(), intervals.end(), myCmp);
        vector<Interval> ans;
        int cnt = 0;
        while(cnt < intervals.size() )
        {
            Interval tmp;
            tmp = intervals[cnt];
            while(cnt + 1 < intervals.size() && intervals[cnt + 1].start <= tmp.end )
            {
                if (intervals[cnt + 1].end >= tmp.end)
                    {tmp.end = intervals[cnt + 1].end;cnt++;}
                else cnt++; // 排除下一个区间已经被上一个区间包围的例子
            }
            cnt++;// 记得要再加一，从下一个开始
            ans.push_back(tmp);
        }
        return ans;
    }
};

更详细请参见这位

/**
 * 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 {
private:
    static bool comp(Interval a, Interval b)
    {
        return a.start < b.start;
    }
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        if(intervals.empty())return intervals;
        sort(intervals.begin(), intervals.end(), comp);
        vector<Interval> res;
        res.push_back(intervals[0]);
        for(int i = 1; i < intervals.size(); i++)
        {
            Interval &p = res.back(); // 找到末尾，为了和下一个开头比较
            if(intervals[i].start > p.end)res.push_back(intervals[i]);
            else if(intervals[i].end > p.end)p.end = intervals[i].end;
        }
        return res;
    }
};