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].
/** * 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: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { } };
我一开始的想法是从头开始遍历 intervals, 找到和newInterval 出现overlap的Interval (哪怕有一个数字相同也算overlap)，记下第一次出现overlap的index，存入startRangeIndex，再找到最后一个和newInterval有overlap的Interval，记为endRangeIndex。最后弹出有overlap的Interval，和newInterval总和并后插入。
这种方法的代码:
/** * 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: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { int i = 0, j = 0; if(intervals.size() == 0) {intervals.push_back(newInterval); return intervals;} int inRangeStart = -1, inRangeEnd = -1; //index range of intervals who have overlaps with newIntervals. int nstart = newInterval.start, nend = newInterval.end; for(; i < intervals.size() && nend >= intervals[i].start; ++i){ if(!(nstart > intervals[i].end || nend < intervals[i].start)){ if(inRangeStart < 0) inRangeStart = i; } } if(inRangeStart >= 0) inRangeEnd = i-1; if(inRangeStart >= 0){ Interval iv(min(nstart, intervals[inRangeStart].start), max(nend, intervals[inRangeEnd].end)); for(int j = 0; j < (inRangeEnd - inRangeStart + 1); ++j) intervals.erase(intervals.begin()+inRangeStart); intervals.insert(intervals.begin()+inRangeStart, iv); }else{ if(i == intervals.size()) intervals.push_back(newInterval); else intervals.insert(intervals.begin() + i, newInterval); } return intervals; } };
结果这种做法在过大数据时超时。原因应该是在原Interval上erase和insert操作比较占用时间。
如果新建一个v来做的话，这种方法需要两次遍历，一次寻找 startRangeIndex 和endRangeIndex， 一次插入。
后来上网搜了搜，参考了http://fisherlei.blogspot.com/2012/12/leetcode-insert-interval.html 的方法，他新定义一个vector<Interval> res来存放结果，遍历Intervals的过程中，将Interval[i]和res的最后一个元素比较，然后重新合并后插入res最末端。
参考这个思路的代码：
/** * 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: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { int j = 0; if(intervals.size() == 0) {intervals.push_back(newInterval); return intervals;} bool neverOverlap = false; vector<Interval> res; for(vector<Interval>::iterator i = intervals.begin(); i < intervals.end(); ++i){ if(neverOverlap) {res.push_back(*i); continue;} if(res.size() != 0){ newInterval = res.back(); res.pop_back(); } if((*i).start > newInterval.end){ res.push_back(newInterval); res.push_back(*i); neverOverlap = true; }else if((*i).end < newInterval.start){ res.push_back(*i); res.push_back(newInterval); }else{ int nstart = min((*i).start, newInterval.start); int nend = max((*i).end, newInterval.end); if(nend == (*i).end) neverOverlap = true; res.push_back(Interval(nstart, nend)); } } return res; } };
[LeetCode] Insert Interval 边插入边merge,布布扣,bubuko.com
[LeetCode] Insert Interval 边插入边merge
原文：http://www.cnblogs.com/felixfang/p/3693271.html