题目：给定一连串的区间，要求输出不重叠的区间。
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 = ;
while(cnt < intervals.size() )
{
Interval tmp;
tmp = intervals[cnt];
while(cnt + < intervals.size() && intervals[cnt + ].start <= tmp.end )
{
if (intervals[cnt + ].end >= tmp.end)
{tmp.end = intervals[cnt + ].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[]);
for(int i = ; 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;
}
};