【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;
}