Redian新闻
>
leetcode 这题insert interval怎么做?
avatar
leetcode 这题insert interval怎么做?# JobHunting - 待字闺中
z*8
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].
代码不好写啊, 谁给贴个?
avatar
i*e
4
会更新的,现在在做后台的东西,等 OJ 系统稳定了就可以继续写文章。OJ 好用/有用吗?
avatar
b*t
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 的大作中提到】
: 大神真身出现了, 怎么很久没有更新了?
avatar
i*e
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

avatar
d*z
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

avatar
p*2
8
我上次用TreeMap写了一个。很简单。一会儿看看能不能找到。
avatar
i*e
9
是用区间树吗?

【在 p*****2 的大作中提到】
: 我上次用TreeMap写了一个。很简单。一会儿看看能不能找到。
avatar
p*2
10

不是区间树。上次有人提到这个idea,我就做了一下,果然很容易。
TreeMap key store start, value store end.
找了好几次也找不到那个帖子了。没准给删掉了。

【在 i**********e 的大作中提到】
: 是用区间树吗?
avatar
n*o
11
你们几个是故意合伙害人的吧?
这种code写出来面试估计就挂了一半了。。。

【在 d****z 的大作中提到】
: zan
avatar
b*t
12
是明显有可以改进的地方的 但是先写个能work的再优化也行吧

【在 n****o 的大作中提到】
: 你们几个是故意合伙害人的吧?
: 这种code写出来面试估计就挂了一半了。。。

avatar
h*l
13
这个先插入是o(nlogn)复杂度把
不是o(n)吗?

【在 i**********e 的大作中提到】
: 恩,对。这个也可以,思路更简洁一些。虽然要遍历两遍。
: 我也是写 merge intervals 的时候想到了。
: 就是先插入并保持排序的条件,然后一个一个 merge,要稍微好写。
: 赞:用了 STL 的 lower_bound,之前还真没见过有这个.

avatar
i*e
14
插入是 O(n),如果给定区间是依start point来排序的话。

【在 h**********l 的大作中提到】
: 这个先插入是o(nlogn)复杂度把
: 不是o(n)吗?

avatar
h*l
15
ok
反正最后肯定是 o(n)解

【在 i**********e 的大作中提到】
: 插入是 O(n),如果给定区间是依start point来排序的话。
avatar
f*i
16
我觉得这个题目如果把给定的intervals分成两类,一类是overlap新interval的,另一
类是和新interval不相关的,那么就可以大大简化bounder condition的判断。
我写了一个O(n)复杂度的程序,和我的思路,放在 http://csjobinterview.wordpress.com/2012/03/28/intervals-merge-problem/ 请大家不吝赐教。
avatar
p*2
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);
}
avatar
i*e
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)

avatar
h*f
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.
avatar
p*2
20

刚才读了一下。逻辑简化的很赞,但是面试的时候可能会不满足附加要求。

【在 i**********e 的大作中提到】
: 火鸡的代码你读了吗?
avatar
i*e
21
你指的附加要求是 in-place merge 吗?

【在 p*****2 的大作中提到】
:
: 刚才读了一下。逻辑简化的很赞,但是面试的时候可能会不满足附加要求。

avatar
p*2
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 吗?
avatar
h*g
23
感觉挺简单的,不知道我的理解是否对
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Interval
{
int left;
int right;
Interval(int left,int right):left(left),right(right)
{
}
};
/////////////////
void merge_nosort(vector in,Interval * s)
{
int left=s->left;
int right=s->right;
vector out;
for(int i=0;i{
if(left>in[i]->right||rightleft)
{
{
out.push_back(in[i]);
}
}
else
{
left=left>in[i]->left?in[i]->left:left;
right=right>in[i]->right?right:in[i]->right;
}
}
out.push_back(new Interval(left,right));
for(int i=0;i{
cout<left<right<}
}
////////////////////////////////////////
int main()
{
Interval *v1=new Interval(2,5);
Interval *v2=new Interval(8,10);
Interval *v3=new Interval(12,15);
Interval *v4=new Interval(50,67);
vector buf;
buf.push_back(v2);
buf.push_back(v1);
buf.push_back(v3);
merge_nosort(buf,v4);
}

【在 p*****2 的大作中提到】
:
: 这道题我碰到过三次。有些要求
: 1.自己设计数据结构。所以不一定用List。按道理来说最好的数据结构是interval
: tree, 但是面试的时候太难写了。所以Treemap是不错的数据结构。数据结构要能够存
: 储,merge这些interval,而不应该每次insert都产生一个新的list。
: 2. interval list可能会非常巨大。因此性能是个问题。TreeMap search, insert,
: delete 都是logn的复杂度。如果用list的话,就应该用binary search了。

avatar
h*g
24
感觉挺简单的,不知道我的理解是否对
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Interval
{
int left;
int right;
Interval(int left,int right):left(left),right(right)
{
}
};
/////////////////
void merge_nosort(vector in,Interval * s)
{
int left=s->left;
int right=s->right;
vector out;
for(int i=0;i{
if(left>in[i]->right||rightleft)
{
{
out.push_back(in[i]);
}
}
else
{
left=left>in[i]->left?in[i]->left:left;
right=right>in[i]->right?right:in[i]->right;
}
}
out.push_back(new Interval(left,right));
for(int i=0;i{
cout<left<right<}
}
////////////////////////////////////////
int main()
{
Interval *v1=new Interval(2,5);
Interval *v2=new Interval(8,10);
Interval *v3=new Interval(12,15);
Interval *v4=new Interval(50,67);
vector buf;
buf.push_back(v2);
buf.push_back(v1);
buf.push_back(v3);
merge_nosort(buf,v4);
}

【在 p*****2 的大作中提到】
:
: 这道题我碰到过三次。有些要求
: 1.自己设计数据结构。所以不一定用List。按道理来说最好的数据结构是interval
: tree, 但是面试的时候太难写了。所以Treemap是不错的数据结构。数据结构要能够存
: 储,merge这些interval,而不应该每次insert都产生一个新的list。
: 2. interval list可能会非常巨大。因此性能是个问题。TreeMap search, insert,
: delete 都是logn的复杂度。如果用list的话,就应该用binary search了。

avatar
g*y
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)

avatar
H*r
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].

avatar
w*x
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]
avatar
i*e
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);

avatar
w*x
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?

avatar
i*e
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)

avatar
l*8
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)复杂度。
: 实现比较麻烦些,不过应该没想象中那么难。我想五十行代码可以写出来,应该是一个
: 很好的编程练习。

avatar
q*y
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;
}
}
avatar
i*e
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;
: }

avatar
i*e
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)复杂度。

avatar
i*e
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();
}
};
avatar
l*8
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 的大作中提到】
: 贴上来让大家学习学习吧。
:
: ".
: '{

avatar
q*y
37
erase的是一个范围,包括所有overlap。代码在leetcode上测试过了。
删除最坏情况是O(nlogn),但考虑一般情况O(logn)插入还是比O(n)要好啊。

【在 i**********e 的大作中提到】
: 用 map/TreeMap 插入区间的 worst case 是 O(n log n).
: 这个worst case 就是当 new_int 覆盖了所有的区间,这时候应该把所有里面的区间删
: 掉。而你代码里面只删掉了一个,所以有问题。

avatar
l*8
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();

avatar
i*e
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)要好啊。

avatar
i*e
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/
avatar
q*y
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/

avatar
M*e
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());
}
}
avatar
i*e
43
你代码写得很好,的确精简。用 key=>value = end=>start 的确简化了好多繁琐的逻
辑。学习了,谢谢。

【在 q***y 的大作中提到】
: 原来map删除单个iterator可以constant time啊,以前没注意。多谢大牛指点。
avatar
l*8
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;
: }

avatar
l*8
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;
: }

avatar
q*y
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;
: }

avatar
l*8
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;
:

avatar
l*8
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;

avatar
k*y
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].

avatar
z*8
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].
代码不好写啊, 谁给贴个?
avatar
i*e
53
会更新的,现在在做后台的东西,等 OJ 系统稳定了就可以继续写文章。OJ 好用/有用吗?
avatar
b*t
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 的大作中提到】
: 大神真身出现了, 怎么很久没有更新了?
avatar
i*e
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

avatar
d*z
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

avatar
p*2
57
我上次用TreeMap写了一个。很简单。一会儿看看能不能找到。
avatar
i*e
58
是用区间树吗?

【在 p*****2 的大作中提到】
: 我上次用TreeMap写了一个。很简单。一会儿看看能不能找到。
avatar
p*2
59

不是区间树。上次有人提到这个idea,我就做了一下,果然很容易。
TreeMap key store start, value store end.
找了好几次也找不到那个帖子了。没准给删掉了。

【在 i**********e 的大作中提到】
: 是用区间树吗?
avatar
n*o
60
你们几个是故意合伙害人的吧?
这种code写出来面试估计就挂了一半了。。。

【在 d****z 的大作中提到】
: zan
avatar
b*t
61
是明显有可以改进的地方的 但是先写个能work的再优化也行吧

【在 n****o 的大作中提到】
: 你们几个是故意合伙害人的吧?
: 这种code写出来面试估计就挂了一半了。。。

avatar
h*l
62
这个先插入是o(nlogn)复杂度把
不是o(n)吗?

【在 i**********e 的大作中提到】
: 恩,对。这个也可以,思路更简洁一些。虽然要遍历两遍。
: 我也是写 merge intervals 的时候想到了。
: 就是先插入并保持排序的条件,然后一个一个 merge,要稍微好写。
: 赞:用了 STL 的 lower_bound,之前还真没见过有这个.

avatar
i*e
63
插入是 O(n),如果给定区间是依start point来排序的话。

【在 h**********l 的大作中提到】
: 这个先插入是o(nlogn)复杂度把
: 不是o(n)吗?

avatar
h*l
64
ok
反正最后肯定是 o(n)解

【在 i**********e 的大作中提到】
: 插入是 O(n),如果给定区间是依start point来排序的话。
avatar
f*i
65
我觉得这个题目如果把给定的intervals分成两类,一类是overlap新interval的,另一
类是和新interval不相关的,那么就可以大大简化bounder condition的判断。
我写了一个O(n)复杂度的程序,和我的思路,放在 http://csjobinterview.wordpress.com/2012/03/28/intervals-merge-problem/ 请大家不吝赐教。
avatar
p*2
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);
}
avatar
i*e
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)

avatar
h*f
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.
avatar
p*2
69

刚才读了一下。逻辑简化的很赞,但是面试的时候可能会不满足附加要求。

【在 i**********e 的大作中提到】
: 火鸡的代码你读了吗?
avatar
i*e
70
你指的附加要求是 in-place merge 吗?

【在 p*****2 的大作中提到】
:
: 刚才读了一下。逻辑简化的很赞,但是面试的时候可能会不满足附加要求。

avatar
p*2
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 吗?
avatar
h*g
72
感觉挺简单的,不知道我的理解是否对
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Interval
{
int left;
int right;
Interval(int left,int right):left(left),right(right)
{
}
};
/////////////////
void merge_nosort(vector in,Interval * s)
{
int left=s->left;
int right=s->right;
vector out;
for(int i=0;i{
if(left>in[i]->right||rightleft)
{
{
out.push_back(in[i]);
}
}
else
{
left=left>in[i]->left?in[i]->left:left;
right=right>in[i]->right?right:in[i]->right;
}
}
out.push_back(new Interval(left,right));
for(int i=0;i{
cout<left<right<}
}
////////////////////////////////////////
int main()
{
Interval *v1=new Interval(2,5);
Interval *v2=new Interval(8,10);
Interval *v3=new Interval(12,15);
Interval *v4=new Interval(50,67);
vector buf;
buf.push_back(v2);
buf.push_back(v1);
buf.push_back(v3);
merge_nosort(buf,v4);
}

【在 p*****2 的大作中提到】
:
: 这道题我碰到过三次。有些要求
: 1.自己设计数据结构。所以不一定用List。按道理来说最好的数据结构是interval
: tree, 但是面试的时候太难写了。所以Treemap是不错的数据结构。数据结构要能够存
: 储,merge这些interval,而不应该每次insert都产生一个新的list。
: 2. interval list可能会非常巨大。因此性能是个问题。TreeMap search, insert,
: delete 都是logn的复杂度。如果用list的话,就应该用binary search了。

avatar
h*g
73
感觉挺简单的,不知道我的理解是否对
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Interval
{
int left;
int right;
Interval(int left,int right):left(left),right(right)
{
}
};
/////////////////
void merge_nosort(vector in,Interval * s)
{
int left=s->left;
int right=s->right;
vector out;
for(int i=0;i{
if(left>in[i]->right||rightleft)
{
{
out.push_back(in[i]);
}
}
else
{
left=left>in[i]->left?in[i]->left:left;
right=right>in[i]->right?right:in[i]->right;
}
}
out.push_back(new Interval(left,right));
for(int i=0;i{
cout<left<right<}
}
////////////////////////////////////////
int main()
{
Interval *v1=new Interval(2,5);
Interval *v2=new Interval(8,10);
Interval *v3=new Interval(12,15);
Interval *v4=new Interval(50,67);
vector buf;
buf.push_back(v2);
buf.push_back(v1);
buf.push_back(v3);
merge_nosort(buf,v4);
}

【在 p*****2 的大作中提到】
:
: 这道题我碰到过三次。有些要求
: 1.自己设计数据结构。所以不一定用List。按道理来说最好的数据结构是interval
: tree, 但是面试的时候太难写了。所以Treemap是不错的数据结构。数据结构要能够存
: 储,merge这些interval,而不应该每次insert都产生一个新的list。
: 2. interval list可能会非常巨大。因此性能是个问题。TreeMap search, insert,
: delete 都是logn的复杂度。如果用list的话,就应该用binary search了。

avatar
g*y
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)

avatar
H*r
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].

avatar
w*x
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]
avatar
i*e
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);

avatar
w*x
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?

avatar
i*e
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)

avatar
l*8
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)复杂度。
: 实现比较麻烦些,不过应该没想象中那么难。我想五十行代码可以写出来,应该是一个
: 很好的编程练习。

avatar
q*y
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;
}
}
avatar
i*e
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;
: }

avatar
i*e
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)复杂度。

avatar
i*e
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();
}
};
avatar
l*8
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 的大作中提到】
: 贴上来让大家学习学习吧。
:
: ".
: '{

avatar
q*y
86
erase的是一个范围,包括所有overlap。代码在leetcode上测试过了。
删除最坏情况是O(nlogn),但考虑一般情况O(logn)插入还是比O(n)要好啊。

【在 i**********e 的大作中提到】
: 用 map/TreeMap 插入区间的 worst case 是 O(n log n).
: 这个worst case 就是当 new_int 覆盖了所有的区间,这时候应该把所有里面的区间删
: 掉。而你代码里面只删掉了一个,所以有问题。

avatar
l*8
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();

avatar
i*e
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)要好啊。

avatar
i*e
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/
avatar
q*y
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/

avatar
M*e
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());
}
}
avatar
i*e
92
你代码写得很好,的确精简。用 key=>value = end=>start 的确简化了好多繁琐的逻
辑。学习了,谢谢。

【在 q***y 的大作中提到】
: 原来map删除单个iterator可以constant time啊,以前没注意。多谢大牛指点。
avatar
l*8
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;
: }

avatar
l*8
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;
: }

avatar
q*y
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;
: }

avatar
l*8
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;
:

avatar
l*8
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;

avatar
k*y
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].

avatar
s*y
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;

avatar
s*y
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;

avatar
s*s
101
onsite时碰到这题,要求在list上改。
void insertInterval (vector &intervals, Interval newInterval);
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。