题解 | #牛舍扩建#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

数组、贪心算法

题目解答方法的文字分析

这道题目可以使用数组和贪心算法来解决。我们可以遍历现有牛舍所占据的区间，分情况讨论如何插入新区间并确保列表中的区间仍然有序且不重叠。

具体步骤如下：

1. 初始化一个空vector res，用于存储最终结果。
2. 遍历现有牛舍所占据的区间：如果当前区间的右边界小于新区间的左边界，表示当前区间在新区间的左侧，将当前区间直接加入res。如果当前区间的左边界大于新区间的右边界，表示当前区间在新区间的右侧，将新区间加入res，并更新新区间为当前区间。如果当前区间与新区间有交集，将新区间的左边界更新为当前区间和新区间左边界的较小值，将新区间的右边界更新为当前区间和新区间右边界的较大值。
3. 将新区间加入res，表示插入新区间后的结果。
4. 返回res，表示最终结果。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals int整型vector<vector<>> 
     * @param new_interval int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int>> insertNewInterval(vector<vector<int>>& intervals, vector<int>& new_interval) {
        vector<vector<int>> res;
        int n = intervals.size();
        int i = 0;

        // 将左边界小于新区间左边界的区间直接加入res
        while (i < n && intervals[i][1] < new_interval[0]) {
            res.push_back(intervals[i]);
            i++;
        }

        // 更新新区间的左边界和右边界
        while (i < n && intervals[i][0] <= new_interval[1]) {
            new_interval[0] = min(new_interval[0], intervals[i][0]);
            new_interval[1] = max(new_interval[1], intervals[i][1]);
            i++;
        }

        // 将更新后的新区间加入res
        res.push_back(new_interval);

        // 将右边界大于新区间右边界的区间加入res
        while (i < n) {
            res.push_back(intervals[i]);
            i++;
        }

        return res;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！