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).

http://www.lintcode.com/en/problem/insert-interval/

Discussion

从左向右遍历intervals，只要满足interval.end < newInterval.start,直接记录下来。
接下来就是处理over-lap的部分，这里比较trick，当前interval已经不能直接插入了，这时候over-lap的start应该是当前interval和newInterval两者的start的最小值，然后看如果interval.start <= newInterval.end（注意这里有个等于号），就一直右移，找overlap的end。

class Solution {
public:
    /**
     * Insert newInterval into intervals.
     * @param intervals: Sorted interval list.
     * @param newInterval: new interval.
     * @return: A new interval list.
     */
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> result;
        size_t i = 0;
        size_t n = intervals.size();
        //keep left part < newInterval.start
        while(i<n && intervals[i].end < newInterval.start) {
            result.emplace_back(intervals[i]);
            i++;
        }
        //deal with newInterval, merge intervals if over lap with newInterval
        while(i<n && intervals[i].start <= newInterval.end) {//刚开始忘记了=
            newInterval = Interval(min(intervals[i].start, newInterval.start),
            max(intervals[i].end, newInterval.end));
            i++;
        }
        result.emplace_back(newInterval);
        //deal with interval left
        if(i<n) {
            result.insert(result.end(), intervals.begin()+i, intervals.end());
        }
        return result;
    }
};

Follow up

上述算法复杂度O(N)，还有改进的余地，能不能直接找到newInterval.start应该插入的位置？因为已知的intervals已经是有序的了，可以用二分查找花费O（logN)的时间找到。
newInterval.start插入的位置是第一个不满足interval.end < newInterval.start的地方。类似的思路也可以用来找newInterval.end

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
class Solution {
public:
    /**
     * Insert newInterval into intervals.
     * @param intervals: Sorted interval list.
     * @param newInterval: new interval.
     * @return: A new interval list.
     */
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        int n = intervals.size();
        int s = 0; 
        int e = n-1;
        vector<Interval> result;
        if(n==0) {//二分查找不能应用于输入为空的情况，或者说需要单独排除这种corner case
            result.emplace_back(newInterval);
            return result;
        }
        //find left part: intervals[i].end < newInterval.start
        //以下是找最后一个满足intervals[i].end < newInterval.start的i
        int i = 0;
        while(s + 1 < e) {
            int mid = s + (e-s)/2;
            if(intervals[mid].end < newInterval.start) {
                s = mid;
            } else {
                e = mid;
            }
        }
        if(intervals[e].end < newInterval.start) {
            i = e;
        } else if(intervals[s].end < newInterval.start) {
            i = s;
        } else {//没有找到，那就不用copy左边了，所以i=-1
            i = -1;
        }
        i++;
        result.insert(result.end(), intervals.begin(), intervals.begin()+i);
        /*****
        如果是这样理解，找第一个满足intervals[i].end >= newInterval.start的i，那么上面那段程序应该这样写了：
        while(s + 1 < e) {
            int mid = s + (e-s)/2;
            if(intervals[mid].end < newInterval.start) {
                s = mid;
            } else {
                e = mid;
            }
        }
        if(intervals[s].end >= newInterval.start) {
            i = s;
        } else if(intervals[e].end >= newInterval.start) {
            i = e;
        } else {
            i = n;
        }
        result.insert(result.end(), intervals.begin(), intervals.begin()+i);
        */
        //deal with newInterval, merge intervals if over lap with newInterval
        while(i<n && intervals[i].start <= newInterval.end) {//刚开始忘记了=
            newInterval = Interval(min(intervals[i].start, newInterval.start),
            max(intervals[i].end, newInterval.end));
            i++;
        }
        result.emplace_back(newInterval);
        //deal with interval left
        if(i<n) {
            result.insert(result.end(), intervals.begin()+i, intervals.end());
        }
        return result;
    }
};