leetcode 56. Merge Intervals 、57. Insert Interval

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 <= 0)
            return result;
        sort(intervals.begin(),intervals.end(),cmp);
        result.push_back(intervals[0]);
        for(int i = 1;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[0]);
        for(int i = 1;i < intervals.size();i++){
            if(result.back()[1] < intervals[i][0])
                result.push_back(intervals[i]);
            else
                result.back()[1] = max(result.back()[1],intervals[i][1]);
        }
        return result;
    }
    static bool cmp(vector<int> a,vector<int> b){
        return a[0] < b[0] ? 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[0] = min(intervals[cur][0],newInterval[0]);
newInterval[1] = max(intervals[cur][1],newInterval[1]);

第二个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 = 0,n = intervals.size();
        while(cur < n && intervals[cur][1] < newInterval[0])
            result.push_back(intervals[cur++]);
        while(cur < n && newInterval[1] >= intervals[cur][0]){
            newInterval[0] = min(intervals[cur][0],newInterval[0]);
            newInterval[1] = max(intervals[cur][1],newInterval[1]);
            cur++;
        }
        result.push_back(newInterval);
        while(cur < n)
            result.push_back(intervals[cur++]);
        return result;
    }
};

leetcode 56. Merge Intervals 、57. Insert Interval

推荐阅读