https://leetcode.com/problems/insert-interval/

insert-intervals.cc

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
// == sol 1
class Solution {
public:
    vector<Interval> insert(vector<Interval>& ins, Interval newin) {
        int st = newin.start;
        int en = newin.end;        
        // check overlap
        int i = 0;
        int from = ins.size()+1;
        bool overlap = false;
        //vector<int> merge(ins.size(), 0);
        for(; i < ins.size(); i++){     
            //cout<<st<<"--"<<en<<" vs " <<ins[i].start<< "--"<<ins[i].end<<endl;
            if(st <= ins[i].start && ins[i].start <= en){                
                en = max(ins[i].end, en);
                overlap = true; 
                from = min(from, i);
                //merge[i] = 1;
            }
            else if( st <= ins[i].end && ins[i].end <= en){                
                st = min(st, ins[i].start);                
                overlap = true;
                from = min(from, i);
                //merge[i] = 1;
            }
            else if( st >= ins[i].start && en <= ins[i].end){
                st = ins[i].start;                
                en = ins[i].end;                
                overlap = true;
                from = min(from, i);
                i++;
                break;
            }
            if(ins[i].start > en) break;
        }
        ins.insert(ins.begin() + i, Interval(st, en));                
        if(overlap==1) ins.erase(ins.begin() + from, ins.begin() + i);        
        return ins;
    }
};

//== sol 2
class Solution {
public:
    vector<Interval> insert(vector<Interval>& ins, Interval newin) {        
        int i = 0, cur = 0;
        vector<Interval> res;
        for(; i < ins.size(); i++){      
            if(newin.end < ins[i].start){
                res.push_back(ins[i]);                
            }
            else if(newin.start > ins[i].end){
                res.push_back(ins[i]);                
                cur++;
            }
            else{
                newin.start = min(newin.start, ins[i].start);
                newin.end = max(newin.end, ins[i].end);
            }
        }
        res.insert(res.begin()+cur, newin);
        return res;
    }
};