[LeetCode] 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类似，Merge Intervals是将一个区间集合中的可以合并的进行合并，因此，这里可以将这个新区间按其实时间的升序排列插入到区间集合中，然后调用Merge Intervals中的merge()函数，这样未免太简单了哦？

这里采用另外的方法，依次遍历区间集合中的集合，如果集合中的当前区间的起始时间大于新区间的结束时间，说明后面的区间就不用遍历了，此时可以直接推出；否则，就判断当前区间是否与新的区间有重叠，如果有，就可以分别设置第一个和最后一个与新的区间有重叠的迭代器。在循环之外，首先判断是否有区间与新的区间重叠，如果没有，就将新的区间插入到刚最后遍历的区间的前面，否则，说明有区间与新的区间重叠，然后修改第一个与新区间有重叠的区间的起始和结束时间，最后删除中间的区间，然后返回区间集合。

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool is_mixed(const Interval &i1, const Interval &i2)
    {
        if(i1.start > i2.end)
            return false;
        else if(i1.end < i2.start)
            return false;
        else
            return true;
    }

    vector
  
    insert(vector
   
     &intervals, Interval newInterval) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if(intervals.size() == 0) return vector
    
     (1, newInterval); int cnt = 0; bool begin_set= false, end_set = false; vector
     
      ::iterator iter1 = intervals.end(), iter2 = intervals.end(); vector
      
       ::iterator iter; for(iter = intervals.begin(); iter != intervals.end(); ++iter) { if(newInterval.end < (*iter).start) { break; } else { if(is_mixed(newInterval, *iter)) { if(!begin_set) { iter1 = iter; begin_set = true; } else { iter2 = iter; end_set = true; } ++cnt; } } } if(cnt == 0) { intervals.insert(iter, newInterval); return intervals; } (*iter1).start = min(newInterval.start, (*iter1).start); if(end_set) (*iter1).end = max(newInterval.end, (*iter2).end); else (*iter1).end = max(newInterval.end, (*iter1).end); if(end_set && iter1 + 1 != intervals.end()) intervals.erase(iter1 + 1, iter2 + 1); return intervals; } };