Insert Interval

Given a non-overlapping interval list which is sorted by start point.
Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

Example

Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]].
Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]].

 

 
/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
class Solution {
private: 
   bool isOverlap(const Interval &left, const Interval &right) {
       return min(left.end, right.end) >= max(left.start, right.start);
   }
   
   Interval merge(const Interval &left, const Interval &right) {
       return Interval(min(left.start, right.start), max(left.end, right.end));
   }
   
public:
    /**
     * Insert newInterval into intervals.
     * @param intervals: Sorted interval list.
     * @param newInterval: new interval.
     * @return: A new interval list.
     */
    vector insert(vector &intervals, Interval newInterval) {
        vector output;
        
        bool merged = false;
        for(Interval inter : intervals) {
            if (merged || inter.end < newInterval.start)
                output.push_back(inter);
            else {
                 if (isOverlap(inter, newInterval)) {
                     newInterval = merge(inter, newInterval);
                 }
                 else {
                     output.push_back(newInterval);
                     output.push_back(inter);
                     merged = true;
                 }
            }
        }
        
        if (!merged)
           output.push_back(newInterval);
        return output;
    }
};