z*********8
发帖数: 2070 | 1 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].
代码不好写啊， 谁给贴个？ | i**********e
发帖数: 1145 | | z*********8
发帖数: 2070 | 3 大神真身出现了， 怎么很久没有更新了？
【在 i**********e 的大作中提到】
: gloomyturkey 给了非常好的解答：
: http://www.mitbbs.com/article/JobHunting/32077231_0.html
| i**********e
发帖数: 1145 | 4 会更新的，现在在做后台的东西，等 OJ 系统稳定了就可以继续写文章。OJ 好用/有用吗？ | b******t
发帖数: 965 | 5 写个C++的
bool myfunction(Interval a, Interval b) {
return (a.start < b.start);
}
class Solution {
public:
vector insert(vector &intervals, Interval
newInterval) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
intervals.insert(lower_bound(intervals.begin(),intervals.end(),
newInterval,myfunction),newInterval);
vector result;
if(intervals.size()>0)
result.push_back(intervals[0]);
int last=0;
for(int i=1;i
{
if (intervals[i].start>result[last].end)
{
result.push_back(intervals[i]);
last++;
}
else
{
result[last].end=max(intervals[i].end,result[last].end);
}
}
return result;
}
};
【在 z*********8 的大作中提到】
: 大神真身出现了， 怎么很久没有更新了？
| i**********e
发帖数: 1145 | 6 恩，对。这个也可以，思路更简洁一些。虽然要遍历两遍。
我也是写 merge intervals 的时候想到了。
就是先插入并保持排序的条件，然后一个一个 merge，要稍微好写。
赞：用了 STL 的 lower_bound，之前还真没见过有这个.
【在 b******t 的大作中提到】
: 写个C++的
: bool myfunction(Interval a, Interval b) {
: return (a.start < b.start);
: }
: class Solution {
: public:
: vector insert(vector &intervals, Interval
: newInterval) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
| d****z
发帖数: 314 | 7 zan
【在 b******t 的大作中提到】
: 写个C++的
: bool myfunction(Interval a, Interval b) {
: return (a.start < b.start);
: }
: class Solution {
: public:
: vector insert(vector &intervals, Interval
: newInterval) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
| p*****2
发帖数: 21240 | 8 我上次用TreeMap写了一个。很简单。一会儿看看能不能找到。 | i**********e
发帖数: 1145 | 9 是用区间树吗？
【在 p*****2 的大作中提到】
: 我上次用TreeMap写了一个。很简单。一会儿看看能不能找到。
| p*****2
发帖数: 21240 | 10
不是区间树。上次有人提到这个idea，我就做了一下，果然很容易。
TreeMap key store start, value store end.
找了好几次也找不到那个帖子了。没准给删掉了。
【在 i**********e 的大作中提到】
: 是用区间树吗？
| | | n****o
发帖数: 399 | 11 你们几个是故意合伙害人的吧？
这种code写出来面试估计就挂了一半了。。。
【在 d****z 的大作中提到】
: zan
| b******t
发帖数: 965 | 12 是明显有可以改进的地方的 但是先写个能work的再优化也行吧
【在 n****o 的大作中提到】
: 你们几个是故意合伙害人的吧？
: 这种code写出来面试估计就挂了一半了。。。
| h**********l
发帖数: 6342 | 13 这个先插入是o(nlogn)复杂度把
不是o（n)吗？
【在 i**********e 的大作中提到】
: 恩，对。这个也可以，思路更简洁一些。虽然要遍历两遍。
: 我也是写 merge intervals 的时候想到了。
: 就是先插入并保持排序的条件，然后一个一个 merge，要稍微好写。
: 赞：用了 STL 的 lower_bound，之前还真没见过有这个.
| i**********e
发帖数: 1145 | 14 插入是 O(n),如果给定区间是依start point来排序的话。
【在 h**********l 的大作中提到】
: 这个先插入是o(nlogn)复杂度把
: 不是o（n)吗？
| h**********l
发帖数: 6342 | 15 ok
反正最后肯定是 o（n）解
【在 i**********e 的大作中提到】
: 插入是 O(n),如果给定区间是依start point来排序的话。
| f*********i
发帖数: 197 | 16 我觉得这个题目如果把给定的intervals分成两类，一类是overlap新interval的，另一
类是和新interval不相关的，那么就可以大大简化bounder condition的判断。
我写了一个O(n)复杂度的程序，和我的思路，放在 http://csjobinterview.wordpress.com/2012/03/28/intervals-merge-problem/ 请大家不吝赐教。 | p*****2
发帖数: 21240 | 17 刚才又重写了一遍
class Solution1
{
TreeMap tm = new TreeMap();
void insert(Interval interval)
{
Integer prev = tm.floorKey(interval.start);
Integer next = tm.ceilingKey(interval.start);
if (prev != null && tm.get(prev) >= interval.start || next != null
&& interval.end >= next)
{
int start = -1;
if (prev != null && tm.get(prev) >= interval.start)
{
tm.put(prev, Math.max(tm.get(prev), interval.end));
start = prev;
}
else
{
int s = interval.start;
int e = Math.max(interval.end, tm.get(next));
tm.remove(next);
tm.put(s, e);
start = s;
}
while (tm.higherKey(start) != null
&& tm.get(start) >= tm.higherKey(start))
{
tm.put(start, Math.max(tm.get(start), tm.higherEntry(start)
.getValue()));
tm.remove(tm.higherKey(start));
}
}
else
tm.put(interval.start, interval.end);
} | i**********e
发帖数: 1145 | 18 火鸡的代码你读了吗？
【在 p*****2 的大作中提到】
: 刚才又重写了一遍
: class Solution1
: {
: TreeMap tm = new TreeMap();
: void insert(Interval interval)
: {
: Integer prev = tm.floorKey(interval.start);
: Integer next = tm.ceilingKey(interval.start);
: if (prev != null && tm.get(prev) >= interval.start || next != null
: && interval.end >= next)
| h*****f
发帖数: 248 | 19 If it is a doubly linked list, you can insert at O(n) and check the previous
and next nodes to see whether the new node can be merged. | p*****2
发帖数: 21240 | 20
刚才读了一下。逻辑简化的很赞，但是面试的时候可能会不满足附加要求。
【在 i**********e 的大作中提到】
: 火鸡的代码你读了吗？
| | | i**********e
发帖数: 1145 | 21 你指的附加要求是 in-place merge 吗？
【在 p*****2 的大作中提到】
:
: 刚才读了一下。逻辑简化的很赞，但是面试的时候可能会不满足附加要求。
| p*****2
发帖数: 21240 | 22
这道题我碰到过三次。有些要求
1.自己设计数据结构。所以不一定用List。按道理来说最好的数据结构是interval
tree, 但是面试的时候太难写了。所以Treemap是不错的数据结构。数据结构要能够存
储，merge这些interval,而不应该每次insert都产生一个新的list。
2. interval list可能会非常巨大。因此性能是个问题。TreeMap search, insert,
delete 都是logn的复杂度。如果用list的话，就应该用binary search了。
【在 i**********e 的大作中提到】
: 你指的附加要求是 in-place merge 吗？
| h*****g
发帖数: 312 | 23 感觉挺简单的，不知道我的理解是否对
#include
#include
#include
#include
#include | h*****g
发帖数: 312 | 24 感觉挺简单的，不知道我的理解是否对
#include
#include
#include
#include
#include | g**********y
发帖数: 14569 | 25 赞，用tree map是可以直接插入合并。以前我没注意到过这四个函数：
higherKey(), lowerKey(), floorKey(), ceilingKey()
学习了。
【在 p*****2 的大作中提到】
: 刚才又重写了一遍
: class Solution1
: {
: TreeMap tm = new TreeMap();
: void insert(Interval interval)
: {
: Integer prev = tm.floorKey(interval.start);
: Integer next = tm.ceilingKey(interval.start);
: if (prev != null && tm.get(prev) >= interval.start || next != null
: && interval.end >= next)
| H****r
发帖数: 2801 | 26 why not use interval tree?
,[
【在 z*********8 的大作中提到】
: 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].
| w****x
发帖数: 2483 | 27 [sourcecode language="cpp"]
//None overlap segments (5,10)(15,17)(18,25),
//insert (16,35), print out merged result:（5，10）（15，35）
bool intersect(int b1, int e1, int b2, int e2)
{
return max(b1, b2) <= min(e1, e2);
}
void PrintMergRes(int a[], int b[], int n, int nBeg, int nEnd)
{
assert(a && b && n > 0 && nBeg < nEnd);
int i = 0;
while (i < n)
{
if (!intersect(a[i], b[i], nBeg, nEnd)) //no intersect
{
cout<<"("<
i++;
}
else
{
int nSegBeg = nBeg;
int nSegEnd = nEnd;
while (i < n && intersect(nSegBeg, nSegEnd,
a[i], b[i]))
{
nSegBeg = min(nSegBeg, a[i]);
nSegEnd = max(nSegEnd, b[i]);
i++;
}
cout<<"("<
}
}
}
[/sourcecode] | i**********e
发帖数: 1145 | 28 Did you consider the case where the inserted interval may not overlap with
all other existing intervals?
【在 w****x 的大作中提到】
: [sourcecode language="cpp"]
: //None overlap segments (5,10)(15,17)(18,25),
: //insert (16,35), print out merged result:（5，10）（15，35）
: bool intersect(int b1, int e1, int b2, int e2)
: {
: return max(b1, b2) <= min(e1, e2);
: }
: void PrintMergRes(int a[], int b[], int n, int nBeg, int nEnd)
: {
: assert(a && b && n > 0 && nBeg < nEnd);
| w****x
发帖数: 2483 | 29
牛哥啊~~ 这都看出来了, 确实没考虑到, 修改后的代码:
//None overlap segments (5,10)(15,17)(18,25),
//insert (16,35), print out merged result:（5，10）（15，35）
bool intersect(int b1, int e1, int b2, int e2)
{
return max(b1, b2) <= min(e1, e2);
}
void PrintMergRes(int a[], int b[], int n, int nBeg, int nEnd)
{
assert(a && b && n > 0 && nBeg < nEnd);
int i = 0;
while (i < n)
{
if (!intersect(a[i], b[i], nBeg, nEnd)) //no intersect
{
//falls between intervals or at first
if (a[i] > nEnd && (i == 0 || b[i-1] < nBeg))
{
cout<<"("<
cout<<"("<
}
else
cout<<"("<
i++;
}
else
{
int nSegBeg = nBeg;
int nSegEnd = nEnd;
while (i < n && intersect(nSegBeg, nSegEnd, a[i], b[i]))
{
nSegBeg = min(nSegBeg, a[i]);
nSegEnd = max(nSegEnd, b[i]);
i++;
}
cout<<"("<
}
}
//falls after all intervals
if (b[n-1] < nBeg)
cout<<"("<
}
【在 i**********e 的大作中提到】
: Did you consider the case where the inserted interval may not overlap with
: all other existing intervals?
| i**********e
发帖数: 1145 | 30 你那边有个 while 循环，不知道是不是我以下所说的这个意思。
Treemap 是很好，但是要考虑到这 insert 最坏复杂度是 O(n log n)。
给个例子：
当新的 interval 与第一个 interval 相交，那总共要从 treemap 里删除 n 个
intervals。每删除一次是 log(n) 时间，那总复杂度就是 O(n log n) 了。
照理说，还是一个 vector 好，maintain sorted intervals，然后 in-place 插入，O(n)复杂度。
实现比较麻烦些，不过应该没想象中那么难。我想五十行代码可以写出来，应该是一个
很好的编程练习。
【在 p*****2 的大作中提到】
: 刚才又重写了一遍
: class Solution1
: {
: TreeMap tm = new TreeMap();
: void insert(Interval interval)
: {
: Integer prev = tm.floorKey(interval.start);
: Integer next = tm.ceilingKey(interval.start);
: if (prev != null && tm.get(prev) >= interval.start || next != null
: && interval.end >= next)
| | | l*********8
发帖数: 4642 | 31 I implemented a function that use "一个vector maintaining sorted intervals".
But my program is on the paper.
It's about 40 lines of code including '{' and '}' or 28 lines (excluding '{
' and '}' )
，O(n)复杂度。
【在 i**********e 的大作中提到】
: 你那边有个 while 循环，不知道是不是我以下所说的这个意思。
: Treemap 是很好，但是要考虑到这 insert 最坏复杂度是 O(n log n)。
: 给个例子：
: 当新的 interval 与第一个 interval 相交，那总共要从 treemap 里删除 n 个
: intervals。每删除一次是 log(n) 时间，那总复杂度就是 O(n log n) 了。
: 照理说，还是一个 vector 好，maintain sorted intervals，然后 in-place 插入，O(n)复杂度。
: 实现比较麻烦些，不过应该没想象中那么难。我想五十行代码可以写出来，应该是一个
: 很好的编程练习。
| q***y
发帖数: 236 | 32 online数据的话，BST也不错，代码用map也很好写。
void interval_merge(map& pre_ints, Interval new_int)
{
// map
map::iterator m_it = pre_ints.lower_bound(new_int.start);
if (m_it == pre_ints.end() || m_it->second > new_int.end) // no
overlap
{
pre_ints[new_int.end] = new_int.start;
}
else // overlap
{
int start = min(m_it->second, new_int.start);
int end;
map::iterator itup = m_it;
while (itup!=pre_ints.end() && itup->second <= new_int.end)
{
end = max(itup->first, new_int.end);
++itup;
}
pre_ints.erase(m_it, itup);
pre_ints[end] = start;
}
} | i**********e
发帖数: 1145 | 33 用 map/TreeMap 插入区间的 worst case 是 O(n log n).
这个worst case 就是当 new_int 覆盖了所有的区间，这时候应该把所有里面的区间删
掉。而你代码里面只删掉了一个，所以有问题。
【在 q***y 的大作中提到】
: online数据的话，BST也不错，代码用map也很好写。
: void interval_merge(map& pre_ints, Interval new_int)
: {
: // map
: map::iterator m_it = pre_ints.lower_bound(new_int.start);
: if (m_it == pre_ints.end() || m_it->second > new_int.end) // no
: overlap
: {
: pre_ints[new_int.end] = new_int.start;
: }
| i**********e
发帖数: 1145 | 34 贴上来让大家学习学习吧。
".
'{
【在 l*********8 的大作中提到】
: I implemented a function that use "一个vector maintaining sorted intervals".
: But my program is on the paper.
: It's about 40 lines of code including '{' and '}' or 28 lines (excluding '{
: ' and '}' )
:
: ，O(n)复杂度。
| i**********e
发帖数: 1145 | 35 写了一个 O(n) 的 in-place insert。
如果有 overlap 多个区间就左移数组（因为所有overlap区间被merge成一个大区间）
，然后更改第一个overlap的区间。
如果没有overlap的话，那要注意是否在某个区间前面。如果是的话，就右移数组一位
，然后insert。
如果以上两种情况都不符合的话，就简单了。只剩下最后一个可能：
把区间push到最后边。
class Solution {
public:
vector intervals;
void insert(Interval newInterval) {
int n = intervals.size();
for (int i = 0; i < n; i++) {
if (newInterval.end < intervals[i].start) {
moveRight(i, 1);
intervals[i] = newInterval;
return;
} else {
int j = i;
while (i < n && isOverlap(intervals[i], newInterval)) {
newInterval.start = min(newInterval.start, intervals[i].start);
newInterval.end = max(newInterval.end, intervals[i].end);
i++;
}
int numOverlaps = i-j;
if (numOverlaps > 0) {
moveLeft(i, numOverlaps-1);
intervals[j] = newInterval;
return;
}
}
}
intervals.push_back(newInterval);
}
bool isOverlap(Interval a, Interval b) {
return max(a.start, b.start) <= min(a.end, b.end);
}
void moveRight(int startIndex, int k) {
int n = intervals.size();
for (int i = 0; i < k; i++)
intervals.push_back(Interval());
for (int i = n-1+k; i >= startIndex+k; i--)
intervals[i] = intervals[i-k];
}
void moveLeft(int startIndex, int k) {
int n = intervals.size();
for (int i = startIndex-k; i <= n-1-k; i++)
intervals[i] = intervals[i+k];
for (int i = 0; i < k; i++)
intervals.pop_back();
}
}; | l*********8
发帖数: 4642 | 36 下面是我的程序
vector a 存储intervals [a[0] a[1]), [a[2] a[3]), [a[4] a[5]) ....
开始写在纸上，后来在电脑上调试才发现有几个bugs. 一遍写对不容易啊:-(
#include
#include
using namespace std;
void MergeToIntervals(vector & a, int left, int right)
{
int leftIdx = lower_bound(a.begin(), a.end(), left) - a.begin();
int rightIdx = upper_bound(a.begin(), a.end(), right) - a.begin();
int vectorSizeChange = 0;
int leftPos = -1; // left boundary's final position in the vector. -1 means it will not be inserted;
int rightPos = -1;
if ( leftIdx% 2 == 0 ) // need to insert "left" into the vector
leftPos = leftIdx + vectorSizeChange++;
vectorSizeChange -= (rightIdx - leftIdx);
if ( rightIdx % 2 == 0) // need to insert "right" into the vector
rightPos = rightIdx + vectorSizeChange++;
if (vectorSizeChange > 0) {
a.resize(a.size() + vectorSizeChange);
copy_backward(a.begin()+leftIdx, a.end()-vectorSizeChange, a.end());
} else if (vectorSizeChange < 0) {
copy(a.begin()+leftIdx-vectorSizeChange, a.end(), a.begin()+leftIdx);
a.resize(a.size() + vectorSizeChange);
}
if (leftPos >= 0)
a[leftPos] =left;
if (rightPos >= 0)
a[rightPos] = right;
}
【在 i**********e 的大作中提到】
: 贴上来让大家学习学习吧。
:
: ".
: '{
| q***y
发帖数: 236 | 37 erase的是一个范围，包括所有overlap。代码在leetcode上测试过了。
删除最坏情况是O(nlogn)，但考虑一般情况O(logn)插入还是比O(n)要好啊。
【在 i**********e 的大作中提到】
: 用 map/TreeMap 插入区间的 worst case 是 O(n log n).
: 这个worst case 就是当 new_int 覆盖了所有的区间，这时候应该把所有里面的区间删
: 掉。而你代码里面只删掉了一个，所以有问题。
| l*********8
发帖数: 4642 | 38 哦，才发现我没有用leetcode上的函数定义。
我是用自己定义的intervals存储。
【在 l*********8 的大作中提到】
: 下面是我的程序
: vector a 存储intervals [a[0] a[1]), [a[2] a[3]), [a[4] a[5]) ....
: 开始写在纸上，后来在电脑上调试才发现有几个bugs. 一遍写对不容易啊:-(
: #include
: #include
: using namespace std;
: void MergeToIntervals(vector & a, int left, int right)
: {
: int leftIdx = lower_bound(a.begin(), a.end(), left) - a.begin();
: int rightIdx = upper_bound(a.begin(), a.end(), right) - a.begin();
| i**********e
发帖数: 1145 | 39 我仔细读了你代码，你是对的。
其实你算法最坏情况是 O(n) 的。因为删除的时候你传入 iterator，所以删除只需要
constant time.
所以 Map/TreeMap 的确是挺好的数据结构来解决这个问题。
Best case: O(log n), Worst case O(n).
【在 q***y 的大作中提到】
: erase的是一个范围，包括所有overlap。代码在leetcode上测试过了。
: 删除最坏情况是O(nlogn)，但考虑一般情况O(logn)插入还是比O(n)要好啊。
| i**********e
发帖数: 1145 | 40 看错了，你传的是两个 iterator range，复杂度不是 constant，但总的来说总复杂度
应该还是 worst case O(n) 的。
那个 map -> 还是用的挺巧妙的阿，学习了。
For the last version ( erase(first,last) ), logarithmic in container size
plus linear in the distance between first and last.
http://www.cplusplus.com/reference/stl/map/erase/ | | | q***y
发帖数: 236 | 41 原来map删除单个iterator可以constant time啊，以前没注意。多谢大牛指点。
【在 i**********e 的大作中提到】
: 看错了，你传的是两个 iterator range，复杂度不是 constant，但总的来说总复杂度
: 应该还是 worst case O(n) 的。
: 那个 map -> 还是用的挺巧妙的阿，学习了。
: For the last version ( erase(first,last) ), logarithmic in container size
: plus linear in the distance between first and last.
: http://www.cplusplus.com/reference/stl/map/erase/
| M*****e
发帖数: 568 | 42 贴一个我写的inplace merge，个人觉得还比较简明了。O(n)
void NumInterval::MergIntervals(vector & P, NumInterval Q)
{
vector::iterator open, closed;
open = closed = P.begin();
while (open != P.end())
{
if (Q.right < open->left)
{
NumInterval temp = *open;
*closed = Q;
closed++;
Q = temp;
}
else if (Q.left > open->right)
{
*closed = *open;
closed++;
}
else
{
Q.left = min(Q.left, open->left);
Q.right = max(Q.right, open->right);
}
open++;
}
if (closed == P.end())
{
P.push_back(Q);
}
else
{
*closed = Q;
P.erase(++closed, P.end());
}
} | i**********e
发帖数: 1145 | 43 你代码写得很好，的确精简。用 key=>value = end=>start 的确简化了好多繁琐的逻
辑。学习了，谢谢。
【在 q***y 的大作中提到】
: 原来map删除单个iterator可以constant time啊，以前没注意。多谢大牛指点。
| l*********8
发帖数: 4642 | 44 学习了，写得很好。
我稍微改了一下：
void interval_merge(map& pre_ints, Interval new_int)
{
// map
map::iterator m_it = pre_ints.lower_bound(new_int.start);
if (m_it == pre_ints.end() || m_it->second > new_int.end) { // no overlap
pre_ints[new_int.end] = new_int.start;
return;
}
int start = min(m_it->second, new_int.start);
int end = new_int.end;
map::iterator itup = pre_ints.upper_bound(new_int.end);
if (itup != pre_ints.end() && itup->second <= new_int.end) {
end = itup->first;
++itup;
}
pre_ints.erase(m_it, itup);
pre_ints[end] = start;
}
【在 q***y 的大作中提到】
: online数据的话，BST也不错，代码用map也很好写。
: void interval_merge(map& pre_ints, Interval new_int)
: {
: // map
: map::iterator m_it = pre_ints.lower_bound(new_int.start);
: if (m_it == pre_ints.end() || m_it->second > new_int.end) // no
: overlap
: {
: pre_ints[new_int.end] = new_int.start;
: }
| l*********8
发帖数: 4642 | 45 又改一个，不知行否。
void interval_merge(map& pre_ints, Interval new_int)
{
// map
map::iterator itlow = pre_ints.lower_bound(new_int.start);
if (itlow != pre_ints.end())
new_int.start = min(new_int.start, itlow->second);
map::iterator itup = pre_ints.upper_bound(new_int.end);
if (itup != pre_ints.end() && itup->second <= new_int.end)
new_int.end = itup++->first;
pre_ints.erase(itlow, itup);
pre_ints[new_int.end] = new_int.start;
}
overlap
【在 l*********8 的大作中提到】
: 学习了，写得很好。
: 我稍微改了一下：
: void interval_merge(map& pre_ints, Interval new_int)
: {
: // map
: map::iterator m_it = pre_ints.lower_bound(new_int.start);
: if (m_it == pre_ints.end() || m_it->second > new_int.end) { // no overlap
: pre_ints[new_int.end] = new_int.start;
: return;
: }
| q***y
发帖数: 236 | 46 end = itup->first; 这行有问题吧。新插入interval的end可能是overlap中最大的。
还是得比较一下。
可以改成
int temp;
if (itup != pre_ints.end() && itup->second <= new_int.end) {
temp = itup->first;
++itup;
}
end = (temp>end)?temp:end;
overlap
【在 l*********8 的大作中提到】
: 学习了，写得很好。
: 我稍微改了一下：
: void interval_merge(map& pre_ints, Interval new_int)
: {
: // map
: map::iterator m_it = pre_ints.lower_bound(new_int.start);
: if (m_it == pre_ints.end() || m_it->second > new_int.end) { // no overlap
: pre_ints[new_int.end] = new_int.start;
: return;
: }
| l*********8
发帖数: 4642 | 47 itup = pre_ints.upper_bound(new_int.end);
so itup->first > new_int.end or itup==pre_ints.end()
【在 q***y 的大作中提到】
: end = itup->first; 这行有问题吧。新插入interval的end可能是overlap中最大的。
: 还是得比较一下。
: 可以改成
: int temp;
: if (itup != pre_ints.end() && itup->second <= new_int.end) {
: temp = itup->first;
: ++itup;
: }
: end = (temp>end)?temp:end;
:
| l*********8
发帖数: 4642 | 48 I just tried this function with a wrapper on leetcode. It passed all the
tests.
【在 l*********8 的大作中提到】
: 又改一个，不知行否。
: void interval_merge(map& pre_ints, Interval new_int)
: {
: // map
: map::iterator itlow = pre_ints.lower_bound(new_int.start);
: if (itlow != pre_ints.end())
: new_int.start = min(new_int.start, itlow->second);
: map::iterator itup = pre_ints.upper_bound(new_int.end);
: if (itup != pre_ints.end() && itup->second <= new_int.end)
: new_int.end = itup++->first;
| k*****y
发帖数: 744 | 49 用stl写个练练手。
struct cmp_start{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.start < rhs.start;
}
};
struct cmp_end{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.end < rhs.end;
}
};
vector insert(vector &intervals, Interval newInterval) {
vector::iterator lower, upper;
lower = lower_bound(intervals.begin(), intervals.end(),
Interval(newInterval.start, newInterval.start), cmp_
end());
upper = upper_bound(lower, intervals.end(),
Interval(newInterval.end, newInterval.end), cmp_
start());
// [ lower, upper ) intersects the newInterval
if(lower == upper){
intervals.insert(lower, newInterval);
}
else{
newInterval.start = min(lower->start, newInterval.start);
newInterval.end = max((upper-1)->end, newInterval.end);
*lower = newInterval;
intervals.erase(lower+1, upper);
}
return intervals;
}
,[
【在 z*********8 的大作中提到】
: 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].
| z*********8
发帖数: 2070 | 50 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].
代码不好写啊， 谁给贴个？ | | | i**********e
发帖数: 1145 | | z*********8
发帖数: 2070 | 52 大神真身出现了， 怎么很久没有更新了？
【在 i**********e 的大作中提到】
: gloomyturkey 给了非常好的解答：
: http://www.mitbbs.com/article/JobHunting/32077231_0.html
| i**********e
发帖数: 1145 | 53 会更新的，现在在做后台的东西，等 OJ 系统稳定了就可以继续写文章。OJ 好用/有用吗？ | b******t
发帖数: 965 | 54 写个C++的
bool myfunction(Interval a, Interval b) {
return (a.start < b.start);
}
class Solution {
public:
vector insert(vector &intervals, Interval
newInterval) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
intervals.insert(lower_bound(intervals.begin(),intervals.end(),
newInterval,myfunction),newInterval);
vector result;
if(intervals.size()>0)
result.push_back(intervals[0]);
int last=0;
for(int i=1;i
{
if (intervals[i].start>result[last].end)
{
result.push_back(intervals[i]);
last++;
}
else
{
result[last].end=max(intervals[i].end,result[last].end);
}
}
return result;
}
};
【在 z*********8 的大作中提到】
: 大神真身出现了， 怎么很久没有更新了？
| i**********e
发帖数: 1145 | 55 恩，对。这个也可以，思路更简洁一些。虽然要遍历两遍。
我也是写 merge intervals 的时候想到了。
就是先插入并保持排序的条件，然后一个一个 merge，要稍微好写。
赞：用了 STL 的 lower_bound，之前还真没见过有这个.
【在 b******t 的大作中提到】
: 写个C++的
: bool myfunction(Interval a, Interval b) {
: return (a.start < b.start);
: }
: class Solution {
: public:
: vector insert(vector &intervals, Interval
: newInterval) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
| d****z
发帖数: 314 | 56 zan
【在 b******t 的大作中提到】
: 写个C++的
: bool myfunction(Interval a, Interval b) {
: return (a.start < b.start);
: }
: class Solution {
: public:
: vector insert(vector &intervals, Interval
: newInterval) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
| p*****2
发帖数: 21240 | 57 我上次用TreeMap写了一个。很简单。一会儿看看能不能找到。 | i**********e
发帖数: 1145 | 58 是用区间树吗？
【在 p*****2 的大作中提到】
: 我上次用TreeMap写了一个。很简单。一会儿看看能不能找到。
| p*****2
发帖数: 21240 | 59
不是区间树。上次有人提到这个idea，我就做了一下，果然很容易。
TreeMap key store start, value store end.
找了好几次也找不到那个帖子了。没准给删掉了。
【在 i**********e 的大作中提到】
: 是用区间树吗？
| n****o
发帖数: 399 | 60 你们几个是故意合伙害人的吧？
这种code写出来面试估计就挂了一半了。。。
【在 d****z 的大作中提到】
: zan
| | | b******t
发帖数: 965 | 61 是明显有可以改进的地方的 但是先写个能work的再优化也行吧
【在 n****o 的大作中提到】
: 你们几个是故意合伙害人的吧？
: 这种code写出来面试估计就挂了一半了。。。
| h**********l
发帖数: 6342 | 62 这个先插入是o(nlogn)复杂度把
不是o（n)吗？
【在 i**********e 的大作中提到】
: 恩，对。这个也可以，思路更简洁一些。虽然要遍历两遍。
: 我也是写 merge intervals 的时候想到了。
: 就是先插入并保持排序的条件，然后一个一个 merge，要稍微好写。
: 赞：用了 STL 的 lower_bound，之前还真没见过有这个.
| i**********e
发帖数: 1145 | 63 插入是 O(n),如果给定区间是依start point来排序的话。
【在 h**********l 的大作中提到】
: 这个先插入是o(nlogn)复杂度把
: 不是o（n)吗？
| h**********l
发帖数: 6342 | 64 ok
反正最后肯定是 o（n）解
【在 i**********e 的大作中提到】
: 插入是 O(n),如果给定区间是依start point来排序的话。
| f*********i
发帖数: 197 | 65 我觉得这个题目如果把给定的intervals分成两类，一类是overlap新interval的，另一
类是和新interval不相关的，那么就可以大大简化bounder condition的判断。
我写了一个O(n)复杂度的程序，和我的思路，放在 http://csjobinterview.wordpress.com/2012/03/28/intervals-merge-problem/ 请大家不吝赐教。 | p*****2
发帖数: 21240 | 66 刚才又重写了一遍
class Solution1
{
TreeMap tm = new TreeMap();
void insert(Interval interval)
{
Integer prev = tm.floorKey(interval.start);
Integer next = tm.ceilingKey(interval.start);
if (prev != null && tm.get(prev) >= interval.start || next != null
&& interval.end >= next)
{
int start = -1;
if (prev != null && tm.get(prev) >= interval.start)
{
tm.put(prev, Math.max(tm.get(prev), interval.end));
start = prev;
}
else
{
int s = interval.start;
int e = Math.max(interval.end, tm.get(next));
tm.remove(next);
tm.put(s, e);
start = s;
}
while (tm.higherKey(start) != null
&& tm.get(start) >= tm.higherKey(start))
{
tm.put(start, Math.max(tm.get(start), tm.higherEntry(start)
.getValue()));
tm.remove(tm.higherKey(start));
}
}
else
tm.put(interval.start, interval.end);
} | i**********e
发帖数: 1145 | 67 火鸡的代码你读了吗？
【在 p*****2 的大作中提到】
: 刚才又重写了一遍
: class Solution1
: {
: TreeMap tm = new TreeMap();
: void insert(Interval interval)
: {
: Integer prev = tm.floorKey(interval.start);
: Integer next = tm.ceilingKey(interval.start);
: if (prev != null && tm.get(prev) >= interval.start || next != null
: && interval.end >= next)
| h*****f
发帖数: 248 | 68 If it is a doubly linked list, you can insert at O(n) and check the previous
and next nodes to see whether the new node can be merged. | p*****2
发帖数: 21240 | 69
刚才读了一下。逻辑简化的很赞，但是面试的时候可能会不满足附加要求。
【在 i**********e 的大作中提到】
: 火鸡的代码你读了吗？
| i**********e
发帖数: 1145 | 70 你指的附加要求是 in-place merge 吗？
【在 p*****2 的大作中提到】
:
: 刚才读了一下。逻辑简化的很赞，但是面试的时候可能会不满足附加要求。
| | | p*****2
发帖数: 21240 | 71
这道题我碰到过三次。有些要求
1.自己设计数据结构。所以不一定用List。按道理来说最好的数据结构是interval
tree, 但是面试的时候太难写了。所以Treemap是不错的数据结构。数据结构要能够存
储，merge这些interval,而不应该每次insert都产生一个新的list。
2. interval list可能会非常巨大。因此性能是个问题。TreeMap search, insert,
delete 都是logn的复杂度。如果用list的话，就应该用binary search了。
【在 i**********e 的大作中提到】
: 你指的附加要求是 in-place merge 吗？
| h*****g
发帖数: 312 | 72 感觉挺简单的，不知道我的理解是否对
#include
#include
#include
#include
#include | h*****g
发帖数: 312 | 73 感觉挺简单的，不知道我的理解是否对
#include
#include
#include
#include
#include | g**********y
发帖数: 14569 | 74 赞，用tree map是可以直接插入合并。以前我没注意到过这四个函数：
higherKey(), lowerKey(), floorKey(), ceilingKey()
学习了。
【在 p*****2 的大作中提到】
: 刚才又重写了一遍
: class Solution1
: {
: TreeMap tm = new TreeMap();
: void insert(Interval interval)
: {
: Integer prev = tm.floorKey(interval.start);
: Integer next = tm.ceilingKey(interval.start);
: if (prev != null && tm.get(prev) >= interval.start || next != null
: && interval.end >= next)
| H****r
发帖数: 2801 | 75 why not use interval tree?
,[
【在 z*********8 的大作中提到】
: 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].
| w****x
发帖数: 2483 | 76 [sourcecode language="cpp"]
//None overlap segments (5,10)(15,17)(18,25),
//insert (16,35), print out merged result:（5，10）（15，35）
bool intersect(int b1, int e1, int b2, int e2)
{
return max(b1, b2) <= min(e1, e2);
}
void PrintMergRes(int a[], int b[], int n, int nBeg, int nEnd)
{
assert(a && b && n > 0 && nBeg < nEnd);
int i = 0;
while (i < n)
{
if (!intersect(a[i], b[i], nBeg, nEnd)) //no intersect
{
cout<<"("<
i++;
}
else
{
int nSegBeg = nBeg;
int nSegEnd = nEnd;
while (i < n && intersect(nSegBeg, nSegEnd,
a[i], b[i]))
{
nSegBeg = min(nSegBeg, a[i]);
nSegEnd = max(nSegEnd, b[i]);
i++;
}
cout<<"("<
}
}
}
[/sourcecode] | i**********e
发帖数: 1145 | 77 Did you consider the case where the inserted interval may not overlap with
all other existing intervals?
【在 w****x 的大作中提到】
: [sourcecode language="cpp"]
: //None overlap segments (5,10)(15,17)(18,25),
: //insert (16,35), print out merged result:（5，10）（15，35）
: bool intersect(int b1, int e1, int b2, int e2)
: {
: return max(b1, b2) <= min(e1, e2);
: }
: void PrintMergRes(int a[], int b[], int n, int nBeg, int nEnd)
: {
: assert(a && b && n > 0 && nBeg < nEnd);
| w****x
发帖数: 2483 | 78
牛哥啊~~ 这都看出来了, 确实没考虑到, 修改后的代码:
//None overlap segments (5,10)(15,17)(18,25),
//insert (16,35), print out merged result:（5，10）（15，35）
bool intersect(int b1, int e1, int b2, int e2)
{
return max(b1, b2) <= min(e1, e2);
}
void PrintMergRes(int a[], int b[], int n, int nBeg, int nEnd)
{
assert(a && b && n > 0 && nBeg < nEnd);
int i = 0;
while (i < n)
{
if (!intersect(a[i], b[i], nBeg, nEnd)) //no intersect
{
//falls between intervals or at first
if (a[i] > nEnd && (i == 0 || b[i-1] < nBeg))
{
cout<<"("<
cout<<"("<
}
else
cout<<"("<
i++;
}
else
{
int nSegBeg = nBeg;
int nSegEnd = nEnd;
while (i < n && intersect(nSegBeg, nSegEnd, a[i], b[i]))
{
nSegBeg = min(nSegBeg, a[i]);
nSegEnd = max(nSegEnd, b[i]);
i++;
}
cout<<"("<
}
}
//falls after all intervals
if (b[n-1] < nBeg)
cout<<"("<
}
【在 i**********e 的大作中提到】
: Did you consider the case where the inserted interval may not overlap with
: all other existing intervals?
| i**********e
发帖数: 1145 | 79 你那边有个 while 循环，不知道是不是我以下所说的这个意思。
Treemap 是很好，但是要考虑到这 insert 最坏复杂度是 O(n log n)。
给个例子：
当新的 interval 与第一个 interval 相交，那总共要从 treemap 里删除 n 个
intervals。每删除一次是 log(n) 时间，那总复杂度就是 O(n log n) 了。
照理说，还是一个 vector 好，maintain sorted intervals，然后 in-place 插入，O(n)复杂度。
实现比较麻烦些，不过应该没想象中那么难。我想五十行代码可以写出来，应该是一个
很好的编程练习。
【在 p*****2 的大作中提到】
: 刚才又重写了一遍
: class Solution1
: {
: TreeMap tm = new TreeMap();
: void insert(Interval interval)
: {
: Integer prev = tm.floorKey(interval.start);
: Integer next = tm.ceilingKey(interval.start);
: if (prev != null && tm.get(prev) >= interval.start || next != null
: && interval.end >= next)
| l*********8
发帖数: 4642 | 80 I implemented a function that use "一个vector maintaining sorted intervals".
But my program is on the paper.
It's about 40 lines of code including '{' and '}' or 28 lines (excluding '{
' and '}' )
，O(n)复杂度。
【在 i**********e 的大作中提到】
: 你那边有个 while 循环，不知道是不是我以下所说的这个意思。
: Treemap 是很好，但是要考虑到这 insert 最坏复杂度是 O(n log n)。
: 给个例子：
: 当新的 interval 与第一个 interval 相交，那总共要从 treemap 里删除 n 个
: intervals。每删除一次是 log(n) 时间，那总复杂度就是 O(n log n) 了。
: 照理说，还是一个 vector 好，maintain sorted intervals，然后 in-place 插入，O(n)复杂度。
: 实现比较麻烦些，不过应该没想象中那么难。我想五十行代码可以写出来，应该是一个
: 很好的编程练习。
| | | q***y
发帖数: 236 | 81 online数据的话，BST也不错，代码用map也很好写。
void interval_merge(map& pre_ints, Interval new_int)
{
// map
map::iterator m_it = pre_ints.lower_bound(new_int.start);
if (m_it == pre_ints.end() || m_it->second > new_int.end) // no
overlap
{
pre_ints[new_int.end] = new_int.start;
}
else // overlap
{
int start = min(m_it->second, new_int.start);
int end;
map::iterator itup = m_it;
while (itup!=pre_ints.end() && itup->second <= new_int.end)
{
end = max(itup->first, new_int.end);
++itup;
}
pre_ints.erase(m_it, itup);
pre_ints[end] = start;
}
} | i**********e
发帖数: 1145 | 82 用 map/TreeMap 插入区间的 worst case 是 O(n log n).
这个worst case 就是当 new_int 覆盖了所有的区间，这时候应该把所有里面的区间删
掉。而你代码里面只删掉了一个，所以有问题。
【在 q***y 的大作中提到】
: online数据的话，BST也不错，代码用map也很好写。
: void interval_merge(map& pre_ints, Interval new_int)
: {
: // map
: map::iterator m_it = pre_ints.lower_bound(new_int.start);
: if (m_it == pre_ints.end() || m_it->second > new_int.end) // no
: overlap
: {
: pre_ints[new_int.end] = new_int.start;
: }
| i**********e
发帖数: 1145 | 83 贴上来让大家学习学习吧。
".
'{
【在 l*********8 的大作中提到】
: I implemented a function that use "一个vector maintaining sorted intervals".
: But my program is on the paper.
: It's about 40 lines of code including '{' and '}' or 28 lines (excluding '{
: ' and '}' )
:
: ，O(n)复杂度。
| i**********e
发帖数: 1145 | 84 写了一个 O(n) 的 in-place insert。
如果有 overlap 多个区间就左移数组（因为所有overlap区间被merge成一个大区间）
，然后更改第一个overlap的区间。
如果没有overlap的话，那要注意是否在某个区间前面。如果是的话，就右移数组一位
，然后insert。
如果以上两种情况都不符合的话，就简单了。只剩下最后一个可能：
把区间push到最后边。
class Solution {
public:
vector intervals;
void insert(Interval newInterval) {
int n = intervals.size();
for (int i = 0; i < n; i++) {
if (newInterval.end < intervals[i].start) {
moveRight(i, 1);
intervals[i] = newInterval;
return;
} else {
int j = i;
while (i < n && isOverlap(intervals[i], newInterval)) {
newInterval.start = min(newInterval.start, intervals[i].start);
newInterval.end = max(newInterval.end, intervals[i].end);
i++;
}
int numOverlaps = i-j;
if (numOverlaps > 0) {
moveLeft(i, numOverlaps-1);
intervals[j] = newInterval;
return;
}
}
}
intervals.push_back(newInterval);
}
bool isOverlap(Interval a, Interval b) {
return max(a.start, b.start) <= min(a.end, b.end);
}
void moveRight(int startIndex, int k) {
int n = intervals.size();
for (int i = 0; i < k; i++)
intervals.push_back(Interval());
for (int i = n-1+k; i >= startIndex+k; i--)
intervals[i] = intervals[i-k];
}
void moveLeft(int startIndex, int k) {
int n = intervals.size();
for (int i = startIndex-k; i <= n-1-k; i++)
intervals[i] = intervals[i+k];
for (int i = 0; i < k; i++)
intervals.pop_back();
}
}; | l*********8
发帖数: 4642 | 85 下面是我的程序
vector a 存储intervals [a[0] a[1]), [a[2] a[3]), [a[4] a[5]) ....
开始写在纸上，后来在电脑上调试才发现有几个bugs. 一遍写对不容易啊:-(
#include
#include
using namespace std;
void MergeToIntervals(vector & a, int left, int right)
{
int leftIdx = lower_bound(a.begin(), a.end(), left) - a.begin();
int rightIdx = upper_bound(a.begin(), a.end(), right) - a.begin();
int vectorSizeChange = 0;
int leftPos = -1; // left boundary's final position in the vector. -1 means it will not be inserted;
int rightPos = -1;
if ( leftIdx% 2 == 0 ) // need to insert "left" into the vector
leftPos = leftIdx + vectorSizeChange++;
vectorSizeChange -= (rightIdx - leftIdx);
if ( rightIdx % 2 == 0) // need to insert "right" into the vector
rightPos = rightIdx + vectorSizeChange++;
if (vectorSizeChange > 0) {
a.resize(a.size() + vectorSizeChange);
copy_backward(a.begin()+leftIdx, a.end()-vectorSizeChange, a.end());
} else if (vectorSizeChange < 0) {
copy(a.begin()+leftIdx-vectorSizeChange, a.end(), a.begin()+leftIdx);
a.resize(a.size() + vectorSizeChange);
}
if (leftPos >= 0)
a[leftPos] =left;
if (rightPos >= 0)
a[rightPos] = right;
}
【在 i**********e 的大作中提到】
: 贴上来让大家学习学习吧。
:
: ".
: '{
| q***y
发帖数: 236 | 86 erase的是一个范围，包括所有overlap。代码在leetcode上测试过了。
删除最坏情况是O(nlogn)，但考虑一般情况O(logn)插入还是比O(n)要好啊。
【在 i**********e 的大作中提到】
: 用 map/TreeMap 插入区间的 worst case 是 O(n log n).
: 这个worst case 就是当 new_int 覆盖了所有的区间，这时候应该把所有里面的区间删
: 掉。而你代码里面只删掉了一个，所以有问题。
| l*********8
发帖数: 4642 | 87 哦，才发现我没有用leetcode上的函数定义。
我是用自己定义的intervals存储。
【在 l*********8 的大作中提到】
: 下面是我的程序
: vector a 存储intervals [a[0] a[1]), [a[2] a[3]), [a[4] a[5]) ....
: 开始写在纸上，后来在电脑上调试才发现有几个bugs. 一遍写对不容易啊:-(
: #include
: #include
: using namespace std;
: void MergeToIntervals(vector & a, int left, int right)
: {
: int leftIdx = lower_bound(a.begin(), a.end(), left) - a.begin();
: int rightIdx = upper_bound(a.begin(), a.end(), right) - a.begin();
| i**********e
发帖数: 1145 | 88 我仔细读了你代码，你是对的。
其实你算法最坏情况是 O(n) 的。因为删除的时候你传入 iterator，所以删除只需要
constant time.
所以 Map/TreeMap 的确是挺好的数据结构来解决这个问题。
Best case: O(log n), Worst case O(n).
【在 q***y 的大作中提到】
: erase的是一个范围，包括所有overlap。代码在leetcode上测试过了。
: 删除最坏情况是O(nlogn)，但考虑一般情况O(logn)插入还是比O(n)要好啊。
| i**********e
发帖数: 1145 | 89 看错了，你传的是两个 iterator range，复杂度不是 constant，但总的来说总复杂度
应该还是 worst case O(n) 的。
那个 map -> 还是用的挺巧妙的阿，学习了。
For the last version ( erase(first,last) ), logarithmic in container size
plus linear in the distance between first and last.
http://www.cplusplus.com/reference/stl/map/erase/ | q***y
发帖数: 236 | 90 原来map删除单个iterator可以constant time啊，以前没注意。多谢大牛指点。
【在 i**********e 的大作中提到】
: 看错了，你传的是两个 iterator range，复杂度不是 constant，但总的来说总复杂度
: 应该还是 worst case O(n) 的。
: 那个 map -> 还是用的挺巧妙的阿，学习了。
: For the last version ( erase(first,last) ), logarithmic in container size
: plus linear in the distance between first and last.
: http://www.cplusplus.com/reference/stl/map/erase/
| | | M*****e
发帖数: 568 | 91 贴一个我写的inplace merge，个人觉得还比较简明了。O(n)
void NumInterval::MergIntervals(vector & P, NumInterval Q)
{
vector::iterator open, closed;
open = closed = P.begin();
while (open != P.end())
{
if (Q.right < open->left)
{
NumInterval temp = *open;
*closed = Q;
closed++;
Q = temp;
}
else if (Q.left > open->right)
{
*closed = *open;
closed++;
}
else
{
Q.left = min(Q.left, open->left);
Q.right = max(Q.right, open->right);
}
open++;
}
if (closed == P.end())
{
P.push_back(Q);
}
else
{
*closed = Q;
P.erase(++closed, P.end());
}
} | i**********e
发帖数: 1145 | 92 你代码写得很好，的确精简。用 key=>value = end=>start 的确简化了好多繁琐的逻
辑。学习了，谢谢。
【在 q***y 的大作中提到】
: 原来map删除单个iterator可以constant time啊，以前没注意。多谢大牛指点。
| l*********8
发帖数: 4642 | 93 学习了，写得很好。
我稍微改了一下：
void interval_merge(map& pre_ints, Interval new_int)
{
// map
map::iterator m_it = pre_ints.lower_bound(new_int.start);
if (m_it == pre_ints.end() || m_it->second > new_int.end) { // no overlap
pre_ints[new_int.end] = new_int.start;
return;
}
int start = min(m_it->second, new_int.start);
int end = new_int.end;
map::iterator itup = pre_ints.upper_bound(new_int.end);
if (itup != pre_ints.end() && itup->second <= new_int.end) {
end = itup->first;
++itup;
}
pre_ints.erase(m_it, itup);
pre_ints[end] = start;
}
【在 q***y 的大作中提到】
: online数据的话，BST也不错，代码用map也很好写。
: void interval_merge(map& pre_ints, Interval new_int)
: {
: // map
: map::iterator m_it = pre_ints.lower_bound(new_int.start);
: if (m_it == pre_ints.end() || m_it->second > new_int.end) // no
: overlap
: {
: pre_ints[new_int.end] = new_int.start;
: }
| l*********8
发帖数: 4642 | 94 又改一个，不知行否。
void interval_merge(map& pre_ints, Interval new_int)
{
// map
map::iterator itlow = pre_ints.lower_bound(new_int.start);
if (itlow != pre_ints.end())
new_int.start = min(new_int.start, itlow->second);
map::iterator itup = pre_ints.upper_bound(new_int.end);
if (itup != pre_ints.end() && itup->second <= new_int.end)
new_int.end = itup++->first;
pre_ints.erase(itlow, itup);
pre_ints[new_int.end] = new_int.start;
}
overlap
【在 l*********8 的大作中提到】
: 学习了，写得很好。
: 我稍微改了一下：
: void interval_merge(map& pre_ints, Interval new_int)
: {
: // map
: map::iterator m_it = pre_ints.lower_bound(new_int.start);
: if (m_it == pre_ints.end() || m_it->second > new_int.end) { // no overlap
: pre_ints[new_int.end] = new_int.start;
: return;
: }
| q***y
发帖数: 236 | 95 end = itup->first; 这行有问题吧。新插入interval的end可能是overlap中最大的。
还是得比较一下。
可以改成
int temp;
if (itup != pre_ints.end() && itup->second <= new_int.end) {
temp = itup->first;
++itup;
}
end = (temp>end)?temp:end;
overlap
【在 l*********8 的大作中提到】
: 学习了，写得很好。
: 我稍微改了一下：
: void interval_merge(map& pre_ints, Interval new_int)
: {
: // map
: map::iterator m_it = pre_ints.lower_bound(new_int.start);
: if (m_it == pre_ints.end() || m_it->second > new_int.end) { // no overlap
: pre_ints[new_int.end] = new_int.start;
: return;
: }
| l*********8
发帖数: 4642 | 96 itup = pre_ints.upper_bound(new_int.end);
so itup->first > new_int.end or itup==pre_ints.end()
【在 q***y 的大作中提到】
: end = itup->first; 这行有问题吧。新插入interval的end可能是overlap中最大的。
: 还是得比较一下。
: 可以改成
: int temp;
: if (itup != pre_ints.end() && itup->second <= new_int.end) {
: temp = itup->first;
: ++itup;
: }
: end = (temp>end)?temp:end;
:
| l*********8
发帖数: 4642 | 97 I just tried this function with a wrapper on leetcode. It passed all the
tests.
【在 l*********8 的大作中提到】
: 又改一个，不知行否。
: void interval_merge(map& pre_ints, Interval new_int)
: {
: // map
: map::iterator itlow = pre_ints.lower_bound(new_int.start);
: if (itlow != pre_ints.end())
: new_int.start = min(new_int.start, itlow->second);
: map::iterator itup = pre_ints.upper_bound(new_int.end);
: if (itup != pre_ints.end() && itup->second <= new_int.end)
: new_int.end = itup++->first;
| k*****y
发帖数: 744 | 98 用stl写个练练手。
struct cmp_start{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.start < rhs.start;
}
};
struct cmp_end{
inline bool operator()(const Interval lhs, const Interval rhs){
return lhs.end < rhs.end;
}
};
vector insert(vector &intervals, Interval newInterval) {
vector::iterator lower, upper;
lower = lower_bound(intervals.begin(), intervals.end(),
Interval(newInterval.start, newInterval.start), cmp_
end());
upper = upper_bound(lower, intervals.end(),
Interval(newInterval.end, newInterval.end), cmp_
start());
// [ lower, upper ) intersects the newInterval
if(lower == upper){
intervals.insert(lower, newInterval);
}
else{
newInterval.start = min(lower->start, newInterval.start);
newInterval.end = max((upper-1)->end, newInterval.end);
*lower = newInterval;
intervals.erase(lower+1, upper);
}
return intervals;
}
,[
【在 z*********8 的大作中提到】
: 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].
| s*******y
发帖数: 44 | 99 我一开始也是这个思路，顺序遍历，找到左右overlap的interval，然后删除、插入。
查找过程可以用binary search优化到logn。
vector insert(vector &intervals, Interval
newInterval) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = intervals.size();
if (size == 0) {
intervals.push_back(newInterval);
return intervals;
}
int i=0, pos;
while (i < size && intervals[i].end < newInterval.start) i++; //
leftmost to someone's end
if (i == size) { //insert newInterval at the end
intervals.push_back(newInterval);
return intervals;
} else {
newInterval.start = min(intervals[i].start, newInterval.start);
pos = i;
}
while (i < size && intervals[i].start <= newInterval.end) i++; //
rightmost to someone's start
if (pos == i) { //insert newInterval at pos
intervals.insert(intervals.begin() + pos, newInterval);
} else { //merge and insert, remove [pos..i-1] and insert pos
newInterval.end = max(intervals[i-1].end, newInterval.end);
intervals.erase (intervals.begin() + pos, intervals.begin() + i);
intervals.insert(intervals.begin() + pos, newInterval);
}
return intervals;
}
【在 i**********e 的大作中提到】
: 写了一个 O(n) 的 in-place insert。
: 如果有 overlap 多个区间就左移数组（因为所有overlap区间被merge成一个大区间）
: ，然后更改第一个overlap的区间。
: 如果没有overlap的话，那要注意是否在某个区间前面。如果是的话，就右移数组一位
: ，然后insert。
: 如果以上两种情况都不符合的话，就简单了。只剩下最后一个可能：
: 把区间push到最后边。
: class Solution {
: public:
: vector intervals;
| s*******y
发帖数: 44 | 100 我一开始也是这个思路，顺序遍历，找到左右overlap的interval，然后删除、插入。
查找过程可以用binary search优化到logn。
vector insert(vector &intervals, Interval
newInterval) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = intervals.size();
if (size == 0) {
intervals.push_back(newInterval);
return intervals;
}
int i=0, pos;
while (i < size && intervals[i].end < newInterval.start) i++; //
leftmost to someone's end
if (i == size) { //insert newInterval at the end
intervals.push_back(newInterval);
return intervals;
} else {
newInterval.start = min(intervals[i].start, newInterval.start);
pos = i;
}
while (i < size && intervals[i].start <= newInterval.end) i++; //
rightmost to someone's start
if (pos == i) { //insert newInterval at pos
intervals.insert(intervals.begin() + pos, newInterval);
} else { //merge and insert, remove [pos..i-1] and insert pos
newInterval.end = max(intervals[i-1].end, newInterval.end);
intervals.erase (intervals.begin() + pos, intervals.begin() + i);
intervals.insert(intervals.begin() + pos, newInterval);
}
return intervals;
}
【在 i**********e 的大作中提到】
: 写了一个 O(n) 的 in-place insert。
: 如果有 overlap 多个区间就左移数组（因为所有overlap区间被merge成一个大区间）
: ，然后更改第一个overlap的区间。
: 如果没有overlap的话，那要注意是否在某个区间前面。如果是的话，就右移数组一位
: ，然后insert。
: 如果以上两种情况都不符合的话，就简单了。只剩下最后一个可能：
: 把区间push到最后边。
: class Solution {
: public:
: vector intervals;
| | | s*********s
发帖数: 318 | 101 onsite时碰到这题，要求在list上改。
void insertInterval (vector &intervals, Interval newInterval)； |
|
