【LeetCode题解】56. Merge Intervals

题意为给定一系列间隔集合，将重叠部分合并

首先判断传入的vector是否为空，若为空则返回它本身

然后根据题目给出的struct定义，可以先将这些间隔根据start的大小进行排序，这一步的实验需要用到stl中的sort函数，并且写出compare函数：

static bool compare(Interval a, Interval b){    if(a.start == b.start) return a.end < b.end;	else return a.start < b.start;}创建新的vector，ret作为待返回的结果，先将intervals[0]插入ret中
然后从intervals的第二项开始比较：
（1）若该项的start值大于ret中最后一项的end值，可以直接将该项插入ret中
（2）若（1）不成立且该项的end值大于ret中最后一项的end值，则用该项的end值更新ret最后一项的end值
（3）若（1）（2）均不成立，则继续比较intervals中的下一项
下面给出代码：
vector<Interval> merge(vector<Interval>& intervals) {    if(intervals.empty())        return intervals;    sort(intervals.begin(), intervals.end(), compare);    int length = intervals.size();    vector<Interval> ret;    ret.push_back(intervals[0]);    int index = 0;    for(int i = 1; i<length; i++){    	if(intervals[i].start > ret[index].end){      		ret.push_back(intervals[i]);       		index++;       		continue;       	}       	else if(intervals[i].end > ret[index].end){       		ret[index].end = intervals[i].end;       		continue;       	}       	else{       		continue;       	}    }    return ret;}