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

分析

无

代码

  1. // Insert Interval
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
  6.         vector<Interval>::iterator it = intervals.begin();
  7.         while (it != intervals.end()) {
  8.             if (newInterval.end < it->start) {
  9.                 intervals.insert(it, newInterval);
  10.                 return intervals;
  11.             } else if (newInterval.start > it->end) {
  12.                 it++;
  13.                 continue;
  14.             } else {
  15.                 newInterval.start = min(newInterval.start, it->start);
  16.                 newInterval.end = max(newInterval.end, it->end);
  17.                 it = intervals.erase(it);
  18.             }
  19.         }
  20.         intervals.insert(intervals.end(), newInterval);
  21.         return intervals;
  22.     }
  23. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/simulation/insert-interval.html