(考前看)57. 插入区间(二分+区间合并)

绝地灬酷狼 2022-10-29 10:29 139阅读 0赞

\#\#\# 解题思路

利用二分法找到合适的位置插入区间

1.枚举特殊情况:插入最左端和插入最右端

2.找到第一个区间,使得区间的右端点大于目标区间的左端点

3.找到第二个区间,使得区间的右端点大于目标区间的右端点

4.处理一种特殊情况,就是这个区间单独成为区间段,不与其他区间合并

\#\#\# 代码

class Solution {
    public:
        int binsearch(int l,int r,int tar,vector<vector<int>>& intervals){
            while(l<r){
                int mid = (l + r) >> 1;
                if(intervals[mid][1] >= tar) r = mid;
                else l = mid + 1;
            }
            return l;
        }
        vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
            vector<vector<int>> res;
            int left = newInterval[0],right = newInterval[1];
            int n = intervals.size();
            if(n == 0){
                res.push_back(newInterval);
                return res;
            }
            //枚举特殊情况:插入最左端和插入最右端
            if(newInterval[1] < intervals[0][0]){
                intervals.insert(intervals.begin(),newInterval);
                return intervals;
            }
            if(newInterval[0] > intervals[n-1][1]){
                intervals.push_back(newInterval);
                return intervals;
            }
            //找到第一个区间,使得区间的右端点大于目标区间的左端点
            int lp = binsearch(0,n-1,left,intervals);
            int rp = binsearch(0,n-1,right,intervals);
            //找到第二个区间,使得区间的右端点大于目标区间的右端点
            for(int i = 0; i < lp; ++i) res.push_back(intervals[i]);
            //处理一种特殊情况,就是这个区间单独成为区间段,不与其他区间合并
            int il,ir,p;
            il = min(intervals[lp][0],newInterval[0]);
            if(newInterval[1] < intervals[rp][0]) ir = newInterval[1],p = rp;
            else ir = max(intervals[rp][1],newInterval[1]),p = rp+1;
            res.push_back({il,ir});
            for(; p < intervals.size();++p) res.push_back(intervals[p]);
            return res; 
        }
    };