题解 | #牛舍扩建# 区间合并

知识点

区间合并

思路

由于原序列已经有序且无重叠，我们只需要找到和新加入的序列有重叠部分的区间后把他们合并即可，没有重叠的部分直接加入答案。遍历一遍数组，时间复杂度为

AC code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals int整型vector<vector<>> 
     * @param new_interval int整型vector 
     * @return int整型vector<vector<>>
     */
    const int INF = 0x3f3f3f3f;
    vector<vector<int> > insertNewInterval(vector<vector<int> >& intervals, vector<int>& new_interval) {
        vector<vector<int>> res;
        int n = intervals.size();
        int st = new_interval[0], ed = new_interval[1];
        for (int i = 0; i < n; i ++) {
            if (intervals[i][1] < new_interval[0]) {
                res.push_back(intervals[i]);
                continue;
            }
            else if (intervals[i][0] > new_interval[1]) {
                if (ed != -INF) {
                    res.push_back({st, ed});
                    ed = -INF;
                } 
                res.push_back(intervals[i]);
                continue;
            }
            st = min(st, intervals[i][0]);
            ed = max(ed, intervals[i][1]);
        }
        if (ed != -INF) res.push_back({st, ed});
        return res;
    }
};