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
Given intervals
[1,3],[6,9]
, insert and merge [2,5]
in as [1,5],[6,9]
.
Example 2:
Given
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
» Solve this problem[4,9]
overlaps with [3,5],[6,7],[8,10]
.[解题思路]
没什么好说的,遍历已有vector,如果当前interval小于newinterval,插入当前;如果当前interval大于newInterval,则插入newInterval及当前;如果两者重叠,merge以后插入新的interval。
实现中之所以重新new了一个vector来存放结果的原因,是不愿意破坏传入参数。
在原有的vector上面直接修改的话,唯一的区别就是,一旦发现当前interval大于newInterval,就应该return了。
[Code]
1: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: vector<Interval> result;
5: result.push_back(newInterval);
6: for(int i=0; i< intervals.size(); i++)
7: {
8: Interval newInt = result.back();
9: result.pop_back();
10: Interval* cur = &intervals[i];
11: if(cur->end < newInt.start)
12: {
13: result.push_back(*cur);
14: result.push_back(newInt);
15: }
16: else if(cur->start > newInt.end)
17: {
18: result.push_back(newInt);
19: result.push_back(*cur);
20: }
21: else
22: {
23: newInt.start = min(cur->start, newInt.start);
24: newInt.end = max(cur->end, newInt.end);
25: result.push_back(newInt);
26: }
27: }
28: return result;
29: }
[发散]
以前换组的时候,面过这道题,但是出题的人,添加了一个附属条件,这些interval是在一个圆环上。比如当环是[1, 255]时,如果两个Interval分别是[1,234], [222, 4], Merge最后的结果是[1,4]。这个条件完全是个干扰,因为如果真的在逻辑中考虑环的话,非常麻烦,而且在环上做循环合并的话,无法判断何时该终止循环。当时我的解法就是,如果第一个是跨越0点的话(比如[234,7]),把它拆分成两个interval([234, 255],[1,7]), 然后把[1,7]插到队头,[234,255]插到队尾。 从[1,7]开始往后合并,合并完成后,再检查对头及队尾,需要的话,再合并一次即可。
Update: 03/14/3013. Refactor code
第一版code因为不了解c++,不知道怎么在iterate vector的过程中做删除,所以引入了多余的空间。后来搜了一下,删除不能再for loop里面做,而要放在while loop中,通过Line 19 返回删除元素下一个元素。
1: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { 2: vector<Interval>::iterator it = intervals.begin(); 3: while(it!= intervals.end()) 4: { 5: if(newInterval.end<it->start) 6: { 7: intervals.insert(it, newInterval); 8: return intervals; 9: } 10: else if(newInterval.start > it->end) 11: { 12: it++; 13: continue; 14: } 15: else 16: { 17: newInterval.start = min(newInterval.start, it->start); 18: newInterval.end = max(newInterval.end, it->end); 19:
it =intervals.erase(it);
20: } 21: } 22: intervals.insert(intervals.end(), newInterval); 23: return intervals; 24: }
No comments:
Post a Comment