LeetCode 57. Insert Interval [Hard] [C++] 解題筆記

這題是 LeetCode 56. Merge Intervals 的進階題，可以先寫寫看喔。

這題給定一些"相互不重疊"(non-overlapping)的區間和一個額外的區間，要求把額外的區間插入並且與原區間集合合併(如果有重疊的話)，這裡題目保證原區間集合中的區間已經按照左端點升序排序好了。

EX:

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

    

    額外的區間[2,5]與原區間集合裡的[1,3]區間重疊所以需要合併。

Ans: [[1,5],[6,9]]

想法:   

    

    簡單的作法是直接把額外的區間插入之後再排序一次，然後問題就變成跟 LeetCode 56. Merge Intervals  一樣了，但因為排序時間複雜度為O(nlogn)。注意到因為題目給的原區間集合的區間已經排序好了，所以我們可以從頭遍歷來找到正確的位置插入區間這樣可以在O(n)的時間內插入且維持排序的結果，或是使用 binary search來找到正確的位置這樣只需要O(logn)的時間，把新區間插入到正確位置之後只需要照 LeetCode 56. Merge Intervals  的算法就可解掉這題。

    這題還有另外一個解法，將原集合分為在新區間左邊,右邊以及重疊的三部份，直接從頭遍歷只要當前區間不與新區間重疊且右端點小於新區間左端點則將該區間放到左邊，若與新區間不重疊且左端點大於新區間右端點則放到右邊，若與新區間重疊則合併。

兩種作法複雜度皆為O(n)，但第二種不用事先插入新區間因此實際runtime可能會快一點點。

Time Complexity: O(n)

完整程式碼:

解法一:

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        // find first element that less than or equal to newInterval's start time
        int lower_bound = 0;
        int left = 0;
        int right = intervals.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (intervals[mid][0] == newInterval[0]) {
                left = mid;
                break;
            }
            else if (intervals[mid][0] < newInterval[0]) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        lower_bound = left;
        intervals.insert(intervals.begin() + lower_bound, newInterval);
        vector<vector<int>> res;
        int left_bnd = intervals[0][0];
        int right_bnd = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            int cur_left = intervals[i][0];
            int cur_right = intervals[i][1];
            // non-overlap
            if (cur_left > right_bnd) {
                vector<int> tmp;
                tmp.emplace_back(left_bnd);
                tmp.emplace_back(right_bnd);
                res.emplace_back(tmp);
                left_bnd = cur_left;
                right_bnd = cur_right;
            }
            else {
                left_bnd = min(left_bnd, cur_left);
                right_bnd = max(right_bnd, cur_right);
            }
        }
        vector<int> tmp;
        tmp.emplace_back(left_bnd);
        tmp.emplace_back(right_bnd);
        res.emplace_back(tmp);
       
        return res;
    }
};

解法二:

class Solution {

public:

    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {

        vector<vector<int>> left;

        vector<vector<int>> right;

        int left_bnd = newInterval[0];

        int right_bnd = newInterval[1];

        for (int i = 0; i < intervals.size(); i++) {

            if (intervals[i][1] < left_bnd) {

                left.emplace_back(intervals[i]);

            }

            else if (intervals[i][0] > right_bnd) {

                right.emplace_back(intervals[i]);

            }

            // overlap

            else {

                left_bnd = min(intervals[i][0], left_bnd);

                right_bnd = max(intervals[i][1], right_bnd);

            }

        }

        // push left intervals

        vector<vector<int>> res(std::move(left));

        // push merged interval

        vector<int> tmp; 

        tmp.emplace_back(left_bnd);

        tmp.emplace_back(right_bnd);

        res.emplace_back(tmp);

        // push right intervals

        res.insert(res.end(), right.begin(), right.end());

        

        return res;

    }

};