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].
题目：插入新区间
思路：感觉这个题做起来比看起来复杂很多。。逻辑上情况比较多，我是遍历给定区间，根据新区间的 start 和 end 相对于当前区间的位置关系，分别处理。特别想说的是：研究了一下用 iterator 遍历 vector，感觉就是个坑，做 insert 、 push_back 、 erase 操作之后需要重新指定 iterator ，好麻烦。最后还是选用下标访问 vector 的方式。标志 isstart 和 isend 用来标记是否处理好新区间的 start / end。另外要考虑清楚插入区间的位置，插入后遍历下标也做相应移动即可。
1 /** 2 * Definition for an interval. 3 * struct Interval { 4 * int start; 5 * int end; 6 * Interval() : start(0), end(0) {} 7 * Interval(int s, int e) : start(s), end(e) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { 13 Interval addinterval; 14 bool isstart = false; 15 bool isend = false; 16 if(!intervals.size()){ 17 intervals.push_back(newInterval); 18 return intervals; 19 } 20 if(newInterval.start <= intervals[0].start && newInterval.end >= intervals[intervals.size()-1].end){ 21 vector<Interval> ret; 22 ret.push_back(newInterval); 23 return ret; 24 } 25 for(int i = 0;i<intervals.size();){ 26 if(newInterval.start < intervals[i].start){ 27 if(newInterval.end < intervals[i].start){ 28 if(!isend){ 29 if(!isstart){ 30 intervals.insert(intervals.begin()+i, newInterval); 31 isstart = true; 32 isend = true; 33 i+=2; 34 } 35 else{ 36 addinterval.end = newInterval.end; 37 intervals.insert(intervals.begin()+i, addinterval); 38 isend = true; 39 break; 40 } 41 } 42 else{ 43 break; 44 } 45 }else if(newInterval.end < intervals[i].end){ 46 if(!isstart){ 47 addinterval.start = newInterval.start; 48 addinterval.end = intervals[i].end; 49 intervals.insert(intervals.begin()+i, addinterval); 50 i++; 51 isstart = true; 52 isend = true; 53 intervals.erase(intervals.begin() + i); 54 break; 55 }else{ 56 if(!isend){ 57 addinterval.end = intervals[i].end; 58 intervals.insert(intervals.begin()+i, addinterval); 59 i++; 60 isend = true; 61 intervals.erase(intervals.begin() + i); 62 } 63 } 64 }else{ 65 intervals.erase(intervals.begin() + i); 66 } 67 }else if(newInterval.start <= intervals[i].end){ 68 if(newInterval.end <= intervals[i].end){ 69 isstart = true; 70 isend = true; 71 break; 72 }else{ 73 addinterval.start = intervals[i].start; 74 isstart = true; 75 intervals.erase(intervals.begin() + i); 76 } 77 }else{ 78 i++; 79 } 80 } 81 82 if(!isstart){ 83 intervals.push_back(newInterval); 84 return intervals; 85 } 86 if(!isend){ 87 addinterval.end = newInterval.end; 88 intervals.push_back(addinterval); 89 return intervals; 90 } 91 return intervals; 92 } 93 };
原文：http://www.cnblogs.com/suwish/p/5229076.html