Insert Interval（C++插入区间）

短命女 2022-10-11 00:59 136阅读 0赞

（1）寻找插入位置+从前一个位置往后合并

class Solution {
    private:
        vector<vector<int>> vec;
    public:
    
        vector<int> helper(vector<int> &a,vector<int> &b) {
            if(a[1]<b[0]) return {-1,-1};
            else if(a[1]==b[0]) return {a[0],b[1]};
            else if(a[1]>=b[1]) return {a[0],a[1]};
            else return {a[0],b[1]};
     
            return {-1,-1};
        }
    
        vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
            if(intervals.size()==0) return {newInterval};
            int index=intervals.size()-1;
            for(int i=0;i<intervals.size();i++) {
                if(newInterval[0]>intervals[i][0]) continue;
                else {
                    index=i-1;
                    break;
                }
            }
    
            vector<int> temp={-1,-1};
            temp[0]=newInterval[0];
            temp[1]=newInterval[1];
            if(index==-1) index=0;
            else {
                temp[0]=intervals[index][0];
                temp[1]=intervals[index][1];
                intervals[index][0]=newInterval[0];
                intervals[index][1]=newInterval[1];
            }
    
            for(int i=0;i<intervals.size();i++) {
                
                if(i<index) vec.push_back(intervals[i]);
                else {
                    vector<int> v=helper(temp,intervals[i]);
                    if(v[0]==-1 && v[1]==-1) {
                        vec.push_back(temp);
                        temp[0]=intervals[i][0];
                        temp[1]=intervals[i][1];
                        if(i==intervals.size()-1) vec.push_back(intervals[i]);
                    } else {
                        temp[0]=v[0];
                        temp[1]=v[1];
                        if(i==intervals.size()-1) vec.push_back(v);
                    } 
                }
            }
    
            return vec;
        }
    };