C++怎么插入?yún)^(qū)間

本篇內(nèi)容介紹了“C++怎么插入?yún)^(qū)間”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

插入?yún)^(qū)間

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

這道題讓我們在一系列非重疊的區(qū)間中插入一個新的區(qū)間，可能還需要和原有的區(qū)間合并，可以對給定的區(qū)間集進(jìn)行一個一個的遍歷比較，那么會有兩種情況，重疊或是不重疊，不重疊的情況最好，直接將新區(qū)間插入到對應(yīng)的位置即可，重疊的情況比較復(fù)雜，有時候會有多個重疊，需要更新新區(qū)間的范圍以便包含所有重疊，之后將新區(qū)間加入結(jié)果 res，最后將后面的區(qū)間再加入結(jié)果 res 即可。具體思路是，用一個變量 cur 來遍歷區(qū)間，如果當(dāng)前 cur 區(qū)間的結(jié)束位置小于要插入的區(qū)間的起始位置的話，說明沒有重疊，則將 cur 區(qū)間加入結(jié)果 res 中，然后 cur 自增1。直到有 cur 越界或有重疊 while 循環(huán)退出，然后再用一個 while 循環(huán)處理所有重疊的區(qū)間，每次用取兩個區(qū)間起始位置的較小值，和結(jié)束位置的較大值來更新要插入的區(qū)間，然后 cur 自增1。直到 cur 越界或者沒有重疊時 while 循環(huán)退出。之后將更新好的新區(qū)間加入結(jié)果 res，然后將 cur 之后的區(qū)間再加入結(jié)果 res 中即可，參見代碼如下：

解法一：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int n = intervals.size(), cur = 0;
        while (cur < n && intervals[cur][1] < newInterval[0]) {
            res.push_back(intervals[cur++]);
        }
        while (cur < n && intervals[cur][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[cur][0]);
            newInterval[1] = max(newInterval[1], intervals[cur][1]);
            ++cur;
        }
        res.push_back(newInterval);
        while (cur < n) {
            res.push_back(intervals[cur++]);
        }
        return res;
    }
};

下面這種方法的思路跟上面的解法很像，只不過沒有用 while 循環(huán)，而是使用的是 for 循環(huán)，但是思路上沒有太大的區(qū)別，變量 cur 還是用來記錄新區(qū)間該插入的位置，稍有不同的地方在于在 for 循環(huán)中已經(jīng)將新區(qū)間后面不重疊的區(qū)間也加進(jìn)去了，for 循環(huán)結(jié)束后就只需要插入新區(qū)間即可，參見代碼如下：

解法二：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int n = intervals.size(), cur = 0;
        for (int i = 0; i < n; ++i) {
            if (intervals[i][1] < newInterval[0]) {
                res.push_back(intervals[i]);
                ++cur;
            } else if (intervals[i][0] > newInterval[1]) {
                res.push_back(intervals[i]);
            } else {
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
            }
        }
        res.insert(res.begin() + cur, newInterval);
        return res;
    }
};

下面這種解法就是把上面解法的 for 循環(huán)改為了 while 循環(huán)，其他的都沒有變，代碼如下：

解法三：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int n = intervals.size(), cur = 0, i = 0;
        while (i < n) {
            if (intervals[i][1] < newInterval[0]) {
                res.push_back(intervals[i]);
                ++cur;
            } else if (intervals[i][0] > newInterval[1]) {
                res.push_back(intervals[i]);
            } else {
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
            }
            ++i;
        }
        res.insert(res.begin() + cur, newInterval);
        return res;
    }
};

“C++怎么插入?yún)^(qū)間”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！