Created
October 30, 2013 16:59
-
-
Save zsh-89/7236175 to your computer and use it in GitHub Desktop.
Leetcode: Insert Interval
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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> &v, Interval x) { | |
vector<Interval> ans; bool in = false; int N = v.size(); | |
for (int i = 0; i < N;) { | |
if (in==false && x.start < v[i].start) { | |
ans.push_back(x); in = true; | |
} else { | |
ans.push_back(v[i]); | |
++i; | |
} | |
} | |
if (in == false) ans.push_back(x); | |
int k = 0; Interval t = ans[0]; | |
for (int i = 1; i < N+1; ++i) { | |
if (ans[i].start <= t.end) { | |
t.end = max(t.end, ans[i].end); | |
} else { | |
ans[k++] = t; t = ans[i]; | |
} | |
} | |
ans[k++] = t; | |
for (int i = 0; i < N+1-k; ++i) | |
ans.pop_back(); | |
return ans; | |
} | |
}; |
这道题和上一道 Merge Intervals 思路一样的。
稍微纠结了一下怎么写才好,最后决定:先把所有的区间都插入vector ans中,再从头到尾合并之。
Nice, 思路就是先Merge Sort,再对Merge Sort完的Array进行Merge Interval。 如果x是一个sorted array也一样
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
这道题和上一道 Merge Intervals 思路一样的。
稍微纠结了一下怎么写才好,最后决定:先把所有的区间都插入vector ans中,再从头到尾合并之。
参照党大的程序,简化了一点写法:其实end max不需要另外设变量,它是隐含在一直维护的『当前区间』(Interval t)中的。