Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

看到这个题目，我首先产生的一个问题就是：是在原来的区间vector上修改，还是重新建一个然后返回？这个问题虽然不会导致算法根本上的差别，但是在实现上却会带来比较大的差别。

关于这个问题，我的想法是：由于传入的参数是引用类型，所以我认为不应该对原来的vector进行修改，而应该新建一个返回。

我的解法是设置两个标志foundStart和foundEnd分别标识是否找到新区间的起始点和终止点是否找到，纯粹地根据区间关系来确定，所以实现起来也相对比较麻烦：

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
    vector<Interval> mergedIntervals;

    int start = 0, end = 0;
    bool foundStart = false, foundEnd = false;
    for (auto interval : intervals) {
        if (!foundStart) {
            if (interval.end < newInterval.start) mergedIntervals.push_back(interval);
            else if (interval.start > newInterval.end) {
                mergedIntervals.push_back(newInterval);
                mergedIntervals.push_back(interval);
                foundStart = true;
                foundEnd = true;
            }
            else {
                start = interval.start < newInterval.start ? interval.start : newInterval.start;
                foundStart = true;
                if (newInterval.end <= interval.end) {
                    mergedIntervals.push_back(Interval(start, interval.end));
                    foundEnd = true;
                }
                else end = newInterval.end;
            }
        }
        else if (!foundEnd) {
            if (interval.start > end) {
                mergedIntervals.push_back(Interval(start, end));
                mergedIntervals.push_back(interval);
                foundEnd = true;
            }
            else if (end < interval.end) {
                mergedIntervals.push_back(Interval(start, interval.end));
                foundEnd = true;
            }
        }
        else mergedIntervals.push_back(interval);
    }

    if (!foundStart) mergedIntervals.push_back(newInterval);
    else if (!foundEnd) mergedIntervals.push_back(Interval(start, end));

    return mergedIntervals;
}

在Discuss上有更好的解法。

LeetCode[Array]: Insert Interval