57. Insert Interval (Array; Project)

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        if(intervals.empty()){
            intervals.push_back(newInterval);
            return intervals;
        }
        int left;
        int right;
        int size1;
        int size2;
        //find the first start which >= newInterval‘s end
        vector<Interval>::iterator itEnd = intervals.begin();
        for(; itEnd < intervals.end();itEnd++)
        {
            if(itEnd->start > newInterval.end) break;
        }
        
        //insert the interval in the way as merge interval
        vector<Interval>::iterator itStart = intervals.begin();
        size2 = newInterval.end - newInterval.start;
        for(; itStart < itEnd;itStart++)
        {
            left = min(itStart->start,newInterval.start);
            right = max(itStart->end,newInterval.end);
            size1 = itStart->end - itStart->start;
            if(right - left > size1 + size2) continue; //no overlapping
            
            //there‘s overlapping
            itStart->start=left;
            itStart->end=right;
            for(vector<Interval>::iterator it = itStart+1; it < itEnd; it++){ //the rest of interval should also merge with the new itStart
                left = min(itStart->start,it->start);
                right = max(itStart->end,it->end);
                size1 = itStart->end - itStart->start;
                size2 = it->end - it->start;
                if(right - left > size1 + size2){ //no more overlapping
                    intervals.erase(itStart+1,it);//erase the elem from itStart+1 to it-1
                    return intervals;
                }
                else{
                    itStart->start=left;
                    itStart->end=right;
                }
            }
            //all overlapping
            intervals.erase(itStart+1,itEnd);//erase the elem from itStart+1 to itEnd-1
            return intervals;
        }
        
        //no overlapping
        intervals.insert(itEnd,newInterval);//insert in the position itEnd
        return intervals;
    }
};