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

这道题的要求是给定一组非重叠且開始时间有序的间隔。在当中插入一个新的间隔。

当然，这道题能够借助里面的代码。先将新的间隔增加到数组中，然后合并就可以。时间复杂度是O(nlogn)。

其实，也能够不排序，直接插入时间间隔。插入的时间间隔的位置能够分成三部分：

  • 插入位置左側
  • 插入位置（有重叠或无重叠）
  • 插入位置右側

这三个部分分别处理，仅仅有在插入位置处理可能存在的情况就可以。

时间复杂度：O(n)

空间复杂度：O(n)

1 class Solution 2 {
        3 public: 4     vector
       
         insert(vector
        
          &intervals, Interval newInterval) 5     {
        6         vector
         
           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 };