56. Merge Intervals是一个无序的，需要将整体合并；57. Insert Interval是一个本身有序的且已经合并好的，需要将新的插入进这个已经合并好的然后合并成新的。
56. Merge Intervals
思路：先根据start升序排序，然后合并
static作用：https://www.cnblogs.com/songdanzju/p/7422380.html
之间写的一个较为复杂的代码
/**
* 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:
vector<Interval> merge(vector<Interval>& intervals) {
vector<Interval> result;
int length = intervals.size();
if(length <= )
return result;
sort(intervals.begin(),intervals.end(),cmp);
result.push_back(intervals[]);
for(int i = ;i < length;i++){
int st = intervals[i].start;
int en = intervals[i].end;
if(st <= result.back().end){
Interval tmp(result.back().start,en);
if(en >= result.back().end){
result.pop_back();
result.push_back(tmp);
}
else
continue;
}
else
result.push_back(intervals[i]);
}
return result;
}
static bool cmp(Interval a,Interval b){
return a.start < b.start;
}
};
http://www.cnblogs.com/grandyang/p/4370601.html
一个更加简洁的代码：
实际上合并的时候，只用考虑两个问题，一是两个有没有交集，即判断前一个的end是否大于后一个的start，如果没有交集直接加入就好了；二是如果有交集，如何合并，首先每一对本身肯定是start小于end，并且排序是根据start升序排的，所以合并之后的start就是前一个的start，而end则取两者的最大的end就好。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
if(intervals.empty())
return result;
sort(intervals.begin(),intervals.end(),cmp);
result.push_back(intervals[]);
for(int i = ;i < intervals.size();i++){
if(result.back()[] < intervals[i][])
result.push_back(intervals[i]);
else
result.back()[] = max(result.back()[],intervals[i][]);
}
return result;
}
static bool cmp(vector<int> a,vector<int> b){
return a[] < b[] ? true : false;
}
};
57. Insert Interval
http://www.cnblogs.com/grandyang/p/4367569.html解法一
这个题可以有一个简单的思路，就是把新的interval按大小插入到原来的intervals组成新的intervals，然后使用merge intervals的方法，但这种方法要使用两个result数组，空间使用的更多。
现在这种方法，只用使用一个result数组。
思路：将跟新interval没有交集的先加入result，然后用新interval合并剩下所有跟他有交集的合并成一个更新的interval然后加入result，最后把剩下的没有交集的加入result中。
第一个while是找没有交集
第二个while是找交集，所以这个判断条件注意一下。
合并的操作代码是：
newInterval[] = min(intervals[cur][],newInterval[]);
newInterval[] = max(intervals[cur][],newInterval[]);
第二个max和56. Merge Intervals使用的是一样的，第一个min之所以这样操作，主要是第一个cur的小值可能在intervals，也可能在newInterval中，后面的小值都在newInterval中
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> result;
if(intervals.empty() && newInterval.empty())
return result;
int cur = ,n = intervals.size();
while(cur < n && intervals[cur][] < newInterval[])
result.push_back(intervals[cur++]);
while(cur < n && newInterval[] >= intervals[cur][]){
newInterval[] = min(intervals[cur][],newInterval[]);
newInterval[] = max(intervals[cur][],newInterval[]);
cur++;
}
result.push_back(newInterval);
while(cur < n)
result.push_back(intervals[cur++]);
return result;
}
};