题解 | #牛舍扩建#

考察的知识点：插入新区间；

解答方法分析：

1. 遍历区间列表，找到新区间需要插入的位置。插入位置可以根据区间的起始端点进行比较，找到第一个起始端点大于新区间起始端点的区间。插入位置为该区间的索引。
2. 在插入位置之前的区间都可以直接添加到结果中。
3. 如果插入位置不是在区间列表的末尾，需要判断新区间是否与插入位置的区间重叠。如果重叠，合并新区间与插入位置的区间，即更新新区间的起始端点和结束端点为两个区间起始端点的较小值和结束端点的较值。
4. 继续遍历后续的区间，如果区间与合并后的新区间重叠，继续合并，更新新区间的起始端点和结束端点。
5. 最后，将合并后的新区间添加到结果中。
6. 如果插入位置不是在区间列表的末尾，将插入位置后的剩余区间添加到结果中。
7. 返回最终的结果。

所用编程语言：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>> result;
        int n = intervals.size();
        int i = 0;
        while (i < n && intervals[i][1] < new_interval[0]) {
            result.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++;
        }
        result.push_back(new_interval);
        while (i < n) {
            result.push_back(intervals[i]);
            i++;
        }
        return result;
    }
};