[LintCode] 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 andnon-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 {
public:
    static bool comp(Interval i1, Interval i2)
    {
        return i1.start < i2.start;
    }
    
    Interval merge(Interval &i1, Interval &i2)
    {
        Interval res(min(i1.start, i2.start), max(i1.end, i2.end));
        return res;
    }
    
    bool hasOverlap(Interval &i1, Interval &i2)
    {
        if(i1.end < i2.start || i2.end < i1.start) return false;
        return true;
    }
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) 
    {
        sort(intervals.begin(), intervals.end(), comp);
        vector<Interval> res;
        for(int i=0;i<intervals.size();i++)
        {
            if(hasOverlap(intervals[i], newInterval))
            {
                newInterval = merge(intervals[i], newInterval);
            }
            else
            {
                res.push_back(intervals[i]);
            }
        }
        int i=0;
        while(i<res.size() && newInterval.end>res[i].start) i++;
        res.insert(res.begin()+i, newInterval);
        return res;
    }
};