logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
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)；
相关阅读
FB 题目问下圣地亚哥12万与奥斯丁9.5万每年，哪个攒钱多？CARLY FIORINA： 魏忠贤穿越 (转载)找个先增后减的数组里的数。OPT快到期了 延期期间 回国问题赚钱神器问一个java的问题请教书单 for becoming a better 程序猿上海 券商 招量化投资经理我难道就要一直相亲么 我已经受不了了身居地下室，忧心万亿公司经营大计内推长期有效 Data Scientist, QDA，UI/UX, Rail, SDE (转载)Facebook system designleetcode要准备收钱了吗？LA的工资和SF工资比例是多少情侣被电击中，居然安然无恙！Facebook's bootcamp and level and packageAmazon算驴还是马?monsanto的scientist职位求内推期望薪水说低了怎么办？【有包子】
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。