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].
这道题的要求是给定一组非重叠且开始时间有序的间隔，在其中插入一个新的间隔。
当然，这道题可以借助Merge Intervals里面的代码，先将新的间隔加入到数组中，然后合并即可。时间复杂度是O(nlogn)。
事实上，也可以不排序，直接插入时间间隔，插入的时间间隔的位置可以分成三部分：
- 插入位置左侧
- 插入位置（有重叠或无重叠）
- 插入位置右侧
这三个部分分别处理，只有在插入位置处理可能存在的情况即可。
时间复杂度：O(n)
空间复杂度：O(n)
1 class Solution
2 {
3 public:
4 vector<Interval> insert(vector<Interval> &intervals, Interval newInterval)
5 {
6 vector<Interval> vi;
7
8 int i = 0;
9 while(i < intervals.size() && intervals[i].end < newInterval.start)
10 vi.push_back(intervals[i ++]);
11
12 vi.push_back(newInterval);
13 while(i < intervals.size() && vi[vi.size() - 1].end >= intervals[i].start)
14 {
15 vi[vi.size() - 1].start = min(intervals[i].start, vi[vi.size() - 1].start);
16 vi[vi.size() - 1].end = max(intervals[i].end, vi[vi.size() - 1].end);
17 ++ i;
18 }
19
20 while(i < intervals.size())
21 vi.push_back(intervals[i ++]);
22
23 return vi;
24 }
25 };