普通数组#中等#合并区间

前文

以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

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

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

正文

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {

    }
};

解法1 将区间表示出来

将区间表示出来即”画”出来，如将所有区间的所有数填充后是：

{0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1}

其中1代表位置上有数，则答案为[[1, 4], [8, 10], [12, 12]]。

但是在代码中采用set数据结构来表示哪有数，选用set是因为其会自动排序，如

// 注意：C++中数组是左右抖括号，博客引擎解析抖括号有问题，这里换成中括号
vector<vector<int>> nums = [[2,2],[2,3],[3,4],[5,5]];
// 表示为：
set{2, 3, 4, 5}
// 即答案为[[2, 5]]

考虑情况：

set{2, 4, 5} -> 答案[[2, 2], [4, 5]]

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {

        if (intervals.size() == 1)
            return intervals;

        vector<vector<int>> res;
        map<int, int> myMap;
        for(auto inter: intervals)
            for(auto i = inter[0]; i <= inter[1]; ++i) {
                if (myMap[i] == 2)
                    continue;
                if (myMap[i] == 1 && myMap[i-1] == 2 && myMap[i+1] == 2) {
                    myMap[i] = 2;
                    continue;
                }
                if (i == inter[0] || i == inter[1]) {
                    myMap[i] = 1;
                } else {
                    myMap[i] = 2;
                }
            }

        vector<int> myVec;
        for (auto m: myMap)
            if (m.second == 1)
                myVec.push_back(m.first);
        // for (auto m: myMap)
        //     cout << m.first << " " << m.second << endl;
        for (auto v: myVec)
            cout << v << ",,";


        // for(auto i = 1; i < myVec.size(); ++i) {

        // }
        // if (myVec.size() == 1)
        //     return [[myVec[0], myVec[0]]];
        
        // int begin = myVec[0], tmp = myVec[0];
        // for(auto i = 1; i < myVec.size(); ++i) {
        //     ++tmp;
        //     if (myVec[i] == tmp && i != myVec.size() - 1)
        //         continue;
        //     if (myVec[i] != tmp) {
        //         res.push_back({begin, myVec[i-1]});
        //         begin = myVec[i];
        //         tmp = myVec[i];
        //     }
        //     if (i == myVec.size() - 1) {
        //         res.push_back({begin, myVec[i]});
        //         break;
        //     }
            
        // }

        return res;
    }
};

这种思路编写的代码无法通过全部测试用例，原因在于：

[[2, 2], [3, 4]] -> set{2, 3, 4} -> 答案无法确定

解法2

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (int i = 0; i < intervals.size(); ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (!merged.size() || merged.back()[1] < L) {
                merged.push_back({L, R});
            }
            else {
                merged.back()[1] = max(merged.back()[1], R);
            }
        }
        return merged;
    }
};

原题解用了排序。