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 <= )

            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;

    }

};

巴特西

leetcode 56. Merge Intervals 、57. Insert Interval

最新文章

热门文章