合并区间-哦吼

合并区间-哦吼

思路

大家应该都感觉到了,此题一定要排序,那么按照左边界排序,还是右边界排序呢?

都可以!

那么我按照左边界排序,排序之后局部最优:每次合并都取最大的右边界,这样就可以合并更多的区间了,整体最优:合并所有重叠的区间。

局部最优可以推出全局最优,找不出反例,试试贪心。

那有同学问了,本来不就应该合并最大右边界么,这和贪心有啥关系?

有时候贪心就是常识!哈哈

按照左边界从小到大排序之后,如果 intervals[i][0] < intervals[i - 1][1] 即intervals[i]左边界 < intervals[i - 1]右边界,则一定有重复,因为intervals[i]的左边界一定是大于等于intervals[i - 1]的左边界。

即:intervals[i]的左边界在intervals[i - 1]左边界和右边界的范围内,那么一定有重复!

这么说有点抽象,看图:(「注意图中区间都是按照左边界排序之后了」)

合并区间-哦吼
知道如何判断重复之后,剩下的就是合并了,如何去模拟合并区间呢?

其实就是用合并区间后左边界和右边界,作为一个新的区间,加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。

写法一

class Solution {
public:
    static bool cmp(vector<int> a,vector<int> b){
       return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        vector<vector<int>> res;
        int Maxright=intervals[0][1];
        int ii=0;
        for(ii=1;ii<intervals.size();ii++){
            if(intervals[ii][0]<=Maxright){
                Maxright=max(intervals[ii][1],intervals[ii-1][1]);
                intervals[ii][0]=min(intervals[ii-1][0],intervals[ii][0]);
                intervals[ii][1]=max(intervals[ii-1][1],intervals[ii][1]);
            }else {
                res.push_back(intervals[ii-1]);
                Maxright=intervals[ii][1];
            }
        }
        res.push_back(intervals[ii-1]);
        return res;
    }
};

写法二

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        if (intervals.size() == 0) return result;
        // 排序的参数使用了lamda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});

        result.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 合并区间
                result.back()[1] = max(result.back()[1], intervals[i][1]);
            } else {
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

时间复杂度:O(nlogn) ,有一个快排
空间复杂度:O(1),不算result数组(返回值所需容器占的空间)

上一篇:LeetCode 56. 合并区间


下一篇:2.合并区间(LeetCode第56题)