【LeetCode 57】插入区间

【题解】

这题要分四种情况。
第一种。区间在所有区间的前面。
第二种。区间在所有区间的后面。
第三种。区间在某两个区间之间但是没有交集。
第四种。区间和某个区间产生了相交。
对于第四种枚举第一次产生相交的区间是哪一个。
然后往后尝试延伸。看看会不会合并更多区间。

【代码】

class Solution {

public:

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

        vector<vector<int>> ans;ans.clear();

        vector<int> temp;temp.resize(2);

        int len = intervals.size();

        //在所有区间前面

        if (!intervals.empty() && newInterval[1]<intervals[0][0]){

            ans.push_back(newInterval);

            for (int i = 0;i<len;i++) ans.push_back(intervals[i]);

            return ans;

        }

        //在区间之间但是没有交集。

        for (int i = 0;i < len-1;i++){

            ans.push_back(intervals[i]);

            if (intervals[i][1]<newInterval[0] &&

                newInterval[1]<intervals[i+1][0]){

                    ans.push_back(newInterval);

                    for (int j = i+1;j<len;j++){

                        ans.push_back(intervals[j]);

                    }

                    return ans;

                }

        }

        ans.clear();

        //区间和某些原来的区间产生了交集。

        for (int i = 0;i < len;i++){

            if (intervals[i][1]>=newInterval[0]){

                int l = min(intervals[i][0],newInterval[0]);

                int r = max(intervals[i][1],newInterval[1]);

                while (i+1<len && intervals[i+1][0]<=r){

                    r = max(r,intervals[i+1][1]);

                    i++;

                }

                temp[0] = l;temp[1] = r;

                ans.push_back(temp);

                for (int j = i+1;j<len;j++) ans.push_back(intervals[j]);

                return ans;

            }else{

                temp = intervals[i];

                ans.push_back(temp);

            }

        }

        ans.push_back(newInterval);

        return ans;

    }

};

巴特西

【LeetCode 57】插入区间

最新文章

热门文章