题目链接：Insert Interval

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution
{
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval)
    {
        vector<Interval> vi;
        
        int i = 0;
        while(i < intervals.size() && intervals[i].end < newInterval.start)
            vi.push_back(intervals[i ++]);
        
        vi.push_back(newInterval);
        while(i < intervals.size() && vi[vi.size() - 1].end >= intervals[i].start)
        {
            vi[vi.size() - 1].start = min(intervals[i].start, vi[vi.size() - 1].start);
            vi[vi.size() - 1].end = max(intervals[i].end, vi[vi.size() - 1].end);
            ++ i;
        }
        
         while(i < intervals.size())
            vi.push_back(intervals[i ++]);
        
        return vi;
    }
};