前言

太久不做题了，这可不是一个好事情。最近刷刷题，尽量做到每日一题肯定做不到。

题目

给出一个区间的集合，请合并所有重叠的区间。

样例

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

分析

大致的思路是先让各区间有序排列，再以某种规则进行无遗漏的区间合并。

得出如下的合并策略：各区间按左端点大小从小到大进行排序。有序后遍历各区间，并维护一个当前区间的结构。在遍历过程中，若下一个区间的左端点值小于等于当前区间的右端点值，则对当前区间右端点进行扩充；不然，则将当前区间压入merged_vector中。

证明这样的遍历合并方法是没有遗漏的：
现有三个有序区间[a1,b1],[a2,b2],[a3,b3]，当前区间为[a1,b1]。
若a2<=b1 ，则合并区间得到当前区间[a1,max(b1,b2)]；
若a2>b1，则有区间有序可知a3>a2>b1，即[a3,b3]∩[a1,b1]为空集。
由递归证明可得证。即遍历过程中不会因为某个区间无法合并导致后续的区间合并被遗漏。

代码

bool cmp(vector<int> a, vector<int> b){
    if(a[0] != b[0]) return a[0] < b[0];
    else return a[1] > b[1];
}

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> merged;
        int size = intervals.size();
        if(size == 0) return merged;
        sort(intervals.begin(), intervals.end(), cmp);
        int current_left,current_right;
        bool hasBreak = false;
        for(int i = 0; i < size; i++){
            current_left = intervals[i][0];
            current_right = intervals[i][1];
            hasBreak = false;
            for(int j = i+1; j < size; j++){
                if(intervals[j][0] <= current_right){
                    current_right = max(current_right, intervals[j][1]);
                    i++;
                }
                else{
                    vector<int> tmp = {current_left, current_right};
                    merged.push_back(tmp);
                    hasBreak = true;
                    break;
                }
            }
        }
        if(hasBreak == false){
            vector<int> tmp = {current_left, current_right};
            merged.push_back(tmp);
        }
        return merged;
    }
};

后续

时间和空间怎么都只击败了10%不到。。。大家的时间复杂度同为O(nlogn)怎么差距这么大呢QAQ。

找了两个答案学习一下。

JackieWu

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {
            return a[0] < b[0];
        });
        vector<vector<int> > ans;
        vector<int> last = std::move(intervals[0]);
        const int N = intervals.size();
        for (int i = 1; i < N; ++i) {
            vector<int> &cur = intervals[i];
            if (cur[0] > last[1]) {
                ans.emplace_back(std::move(last));
                last = std::move(cur);
            } else {
                if (cur[1] > last[1]) last[1] = cur[1];
            }
        }
        ans.emplace_back(std::move(last));
        return ans;
    }
};

蟹黄桑

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> ret;
        for (auto &i : intervals) {
            if (ret.empty() || i[0] > ret.back()[1]) ret.push_back(i);
            else ret.back()[1] = max(i[1], ret.back()[1]);
        }
        return ret;
    }
};

另外遇到了函数对象的问题和reference to non-static member function must be called的问题，真该好好补一下知识了。