题解 | #牛群的合并# 模拟

class Solution {
  private:
    // 判断两个区域是否相交
    bool isIntersect(vector<int>& a, vector<int>& b) {
        if (a[0] < b[0] && a[1] < b[1] && a[1] > b[0]) {
            return true;
        }
        if (a[0] < b[0] && a[1] > b[1]) {
            return true;
        }
        return false;
    }
    // 合并两个区域
    vector<int> merge(vector<int>& a, vector<int>& b) {
        return {min(a[0], b[0]), max(a[1], b[1])};
    }
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grasslands int整型vector<vector<>>
     * @return int整型vector<vector<>>
     */
    vector<vector<int>> mergeGrasslands(vector<vector<int>>& grasslands) {
        sort(grasslands.begin(), grasslands.end(), [&](const auto & a, const auto & b) {
            return a[0] < b[0];
        });
        vector<vector<int>> ans;
        int j;
        vector<int> temp;
        for (int i = 0; i < grasslands.size();) {
            j = i;
            temp = grasslands[j]; // 保存当前合并的区域
            // 找到所有与temp相交的区域，合并进temp中
            while (j < grasslands.size() - 1 &&
                    isIntersect(temp, grasslands[j + 1])) {
                temp = merge(temp, grasslands[j + 1]);
                j++;
            }
            ans.push_back(temp);
            i = j + 1;
        }
        return ans;
    }
};

时间复杂度：

1、对区域按左边界排序的时间复杂度为O(nlogn)，其中n是区域的数量。

2、遍历排序后的草地区域需要O(n)的时间

3、在内部循环中，最坏情况下，每个区域都与前一个区域相交，需要O(n)的时间

因此，总体时间复杂度为O(nlogn)

空间复杂度：临时变量temp和结果向量ans的空间复杂度为O(n)，总体空间复杂度为O(n)