s********u
发帖数: 1109 | 1 感觉这道题经久不衰，一直是经典难题。就是一堆interval，带有start和end，以及高
度，整合之后每个interval要取最高值。
最近换汤不换药，出了speaker的版本：
http://www.mitbbs.com/article_t/JobHunting/32569901.html
epi有两道题，14.19和15.1处理这类问题。
方法是不同的，
一个先将endpoint排序，另外用一个BST维护当前的最大高度，然后结束时就删除相应
的节点，这个感觉很难想，代码简洁一点。
另一个是mergesort。思路简单，代码要冗长一点。
个人感觉前者适用于应付stream，如果是静态数据应该mergesort就够了。
大家怎么看呢？ |
s***e
发帖数: 403 | |
f********e
发帖数: 91 | 3 LZ在看epi吗？里面的题目有些挺难的。。。
【在 s********u 的大作中提到】
: 感觉这道题经久不衰，一直是经典难题。就是一堆interval，带有start和end，以及高
: 度，整合之后每个interval要取最高值。
: 最近换汤不换药，出了speaker的版本：
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: epi有两道题，14.19和15.1处理这类问题。
: 方法是不同的，
: 一个先将endpoint排序，另外用一个BST维护当前的最大高度，然后结束时就删除相应
: 的节点，这个感觉很难想，代码简洁一点。
: 另一个是mergesort。思路简单，代码要冗长一点。
: 个人感觉前者适用于应付stream，如果是静态数据应该mergesort就够了。
|
p*****2
发帖数: 21240 | |
s********u
发帖数: 1109 | 5 epi题目很鲜活，但答案太文艺了。。。。
【在 f********e 的大作中提到】
: LZ在看epi吗？里面的题目有些挺难的。。。
|
s**x
发帖数: 7506 | 6 嗯， 俺学到的就是可以用 ordered set 作 max heap.
ordered set 本身就是 BST, 可以容易的删除一个节点，find the max value using
end() - 1 或 begin() depending on how you define the comparing function.
this is nice.
classical max heap does not support removing random element well. |
s********u
发帖数: 1109 | 7 是的，主要是库里的heap不支持，自己可以写但太麻烦了，要siftup和siftdown。所以
还是bst好维护。对了，取最后一个值的话用rbegin()和end(）-1有什么区别呢
【在 s**x 的大作中提到】
: 嗯， 俺学到的就是可以用 ordered set 作 max heap.
: ordered set 本身就是 BST, 可以容易的删除一个节点，find the max value using
: end() - 1 或 begin() depending on how you define the comparing function.
: this is nice.
: classical max heap does not support removing random element well.
|
g*********e
发帖数: 14401 | 8 这题还可以用divide and conquer做 |
b*******e
发帖数: 123 | |
f********e
发帖数: 91 | 10 恩 里面很多代码都是用template写的，有些挺简练的
【在 s********u 的大作中提到】
: epi题目很鲜活，但答案太文艺了。。。。
|
|
|
s********u
发帖数: 1109 | 11 嗯，就是我说的merge
【在 g*********e 的大作中提到】
: 这题还可以用divide and conquer做
|
J****3
发帖数: 427 | 12 我用 g++ 4.7 测怎么map木有emplace这个函数呢。楼主有碰到吗 |
s********u
发帖数: 1109 | 13 C++11有，是emplace_back吧，其实你就当是push_back吧
【在 J****3 的大作中提到】
: 我用 g++ 4.7 测怎么map木有emplace这个函数呢。楼主有碰到吗
|
f********x
发帖数: 2086 | 14
thanks!
这题学会了
【在 s********u 的大作中提到】
: 感觉这道题经久不衰，一直是经典难题。就是一堆interval，带有start和end，以及高
: 度，整合之后每个interval要取最高值。
: 最近换汤不换药，出了speaker的版本：
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: epi有两道题，14.19和15.1处理这类问题。
: 方法是不同的，
: 一个先将endpoint排序，另外用一个BST维护当前的最大高度，然后结束时就删除相应
: 的节点，这个感觉很难想，代码简洁一点。
: 另一个是mergesort。思路简单，代码要冗长一点。
: 个人感觉前者适用于应付stream，如果是静态数据应该mergesort就够了。
|
J****3
发帖数: 427 | 15 是的 我是用11标准编译的。 map在11里也没emplace_back哇，我是看你发的那个link
上的代码想跑跑他那个例子看。
【在 s********u 的大作中提到】
: C++11有，是emplace_back吧，其实你就当是push_back吧
|
J****3
发帖数: 427 | 16 就insert好了。不懂为啥
【在 s********u 的大作中提到】
: C++11有，是emplace_back吧，其实你就当是push_back吧
|
s********u
发帖数: 1109 | 17 哦哦我傻掉了，是map。其实我一般都是用[]的呵呵。他那个例子我经常跑死机。。。
不知为啥。。
link
【在 J****3 的大作中提到】
: 是的 我是用11标准编译的。 map在11里也没emplace_back哇，我是看你发的那个link
: 上的代码想跑跑他那个例子看。
|
J****3
发帖数: 427 | 18 哈哈， 对啦 上面你们说的用ordered set 做？是指怎么实现？
【在 s********u 的大作中提到】
: 哦哦我傻掉了，是map。其实我一般都是用[]的呵呵。他那个例子我经常跑死机。。。
: 不知为啥。。
:
: link
|
n****e
发帖数: 678 | 19 同感啊，有些答案写得不容易看懂，读起来挺费劲的。
【在 s********u 的大作中提到】
: epi题目很鲜活，但答案太文艺了。。。。
|
s********u
发帖数: 1109 | 20 就是bst，维护一个当前的最大高度，碰到末尾就把他删掉，这时候就能获取次高的高
度。
ordered_set就是一个没有value只有key的bst。但这个题好像的确应该是用map的，除
非你把value整合到set的key里面去。。
【在 J****3 的大作中提到】
: 哈哈， 对啦 上面你们说的用ordered set 做？是指怎么实现？
|
|
|
J****3
发帖数: 427 | 21 恩 这题他也说用height做proxy，也提到height在这里是唯一的， 作为map的key。 不
过map也是rbt。后面有个变体题目是height不唯一的情况
【在 s********u 的大作中提到】
: 就是bst，维护一个当前的最大高度，碰到末尾就把他删掉，这时候就能获取次高的高
: 度。
: ordered_set就是一个没有value只有key的bst。但这个题好像的确应该是用map的，除
: 非你把value整合到set的key里面去。。
|
s********u
发帖数: 1109 | 22 你是说15.1么，嗯。就是我说的mergesort。bst主要是std::map不支持说重复key的情
况。如果自己实现则可以。
【在 J****3 的大作中提到】
: 恩 这题他也说用height做proxy，也提到height在这里是唯一的， 作为map的key。 不
: 过map也是rbt。后面有个变体题目是height不唯一的情况
|
A*********c
发帖数: 430 | 23 emplace_back() 比 push_back()更加效率一点。
新的c++11的feature用gcc 4.8或者比较新的clang++都支持。
【在 J****3 的大作中提到】
: 我用 g++ 4.7 测怎么map木有emplace这个函数呢。楼主有碰到吗
|
A*********c
发帖数: 430 | 24 这题前两天看了一眼，没有思路，就没搞，现在电面都玩这个了？
【在 s********u 的大作中提到】
: 感觉这道题经久不衰，一直是经典难题。就是一堆interval，带有start和end，以及高
: 度，整合之后每个interval要取最高值。
: 最近换汤不换药，出了speaker的版本：
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: epi有两道题，14.19和15.1处理这类问题。
: 方法是不同的，
: 一个先将endpoint排序，另外用一个BST维护当前的最大高度，然后结束时就删除相应
: 的节点，这个感觉很难想，代码简洁一点。
: 另一个是mergesort。思路简单，代码要冗长一点。
: 个人感觉前者适用于应付stream，如果是静态数据应该mergesort就够了。
|
J****3
发帖数: 427 | 25 是这个题答案后面 的e-variant 题吧
【在 s********u 的大作中提到】
: 你是说15.1么，嗯。就是我说的mergesort。bst主要是std::map不支持说重复key的情
: 况。如果自己实现则可以。
|
J****3
发帖数: 427 | 26 这样啊 原来是4.7支持的不够全面？
【在 A*********c 的大作中提到】
: emplace_back() 比 push_back()更加效率一点。
: 新的c++11的feature用gcc 4.8或者比较新的clang++都支持。
|
c********w
发帖数: 2438 | |
A*********c
发帖数: 430 | 28 嗯，我记得好像是4.8才开始支持C++11的。
【在 J****3 的大作中提到】
: 这样啊 原来是4.7支持的不够全面？
|
s********u
发帖数: 1109 | 29 4.7也支持，不全面而已。
【在 A*********c 的大作中提到】
: 嗯，我记得好像是4.8才开始支持C++11的。
|
A*********c
发帖数: 430 | 30 哦，I see。thanks！
【在 s********u 的大作中提到】
: 4.7也支持，不全面而已。
|
|
|
o*****n
发帖数: 189 | 31 这样做可以吗 ？
先把所有的区间切成单位长度。然后，区间的位置作为key, 音量为值。
然后按照key 从小到大， 比较音量，取大值。排成数组。
S1=[[(2,5), 10], [(6,10), 2],[(11, 13), 6]]
S2= [[(1,6),1], [(8,12), 8],[(13,15),3]]
print S1
print S2
def speaker(S1,S2):
res=[]
SN1,SN2=dict(),dict()
for s in S1:
for i in range(s[0][0],s[0][1]):
SN1[i]= s[1]
for s in S2:
for j in range(s[0][0],s[0][1]):
SN2[j]=s[1]
mk=max(SN1.keys()[-1],SN2.keys()[-1])
for k in range(mk+1):
if k in SN1.keys() and k in SN2.keys():
res.append(((k,k+1),max(SN1[k],SN2[k])))
elif k in SN1.keys():
res.append(((k,k+1), SN1[k]))
elif k in SN2.keys():
res.append(((k,k+1), SN2[k]))
return res
print speaker(S1,S2)
output:
[((1, 2), 1), ((2, 3), 10), ((3, 4), 10), ((4, 5), 10), ((5, 6), 1), ((6, 7)
, 2), ((7, 8), 2), ((8, 9), 8), ((9, 10), 8), ((10, 11), 8), ((11, 12), 8),
((12, 13), 6), ((13, 14), 3), ((14, 15), 3)] |
s********u
发帖数: 1109 | 32 可以是可以，复杂度较高。
【在 o*****n 的大作中提到】
: 这样做可以吗 ？
: 先把所有的区间切成单位长度。然后，区间的位置作为key, 音量为值。
: 然后按照key 从小到大， 比较音量，取大值。排成数组。
: S1=[[(2,5), 10], [(6,10), 2],[(11, 13), 6]]
: S2= [[(1,6),1], [(8,12), 8],[(13,15),3]]
: print S1
: print S2
: def speaker(S1,S2):
: res=[]
: SN1,SN2=dict(),dict()
|
p*****3
发帖数: 488 | 33 啥skyline, area of overlapped rectangles, 判断二维线段相交，从上往下看color
啥的，都是一类问题 |
J****3
发帖数: 427 | 34 惊现3爷
color
【在 p*****3 的大作中提到】
: 啥skyline, area of overlapped rectangles, 判断二维线段相交，从上往下看color
: 啥的，都是一类问题
|
J*********r
发帖数: 5921 | |
f*****d
发帖数: 209 | 36 当年面google就碰到这题，那时OJ是啥都不知道，国人mm老说in the right direction
, 面试还延长了5分中，最后还是没弄出来。
这题其实和几道interval的题思路一样，稍微复杂一点。
【在 s********u 的大作中提到】
: 感觉这道题经久不衰，一直是经典难题。就是一堆interval，带有start和end，以及高
: 度，整合之后每个interval要取最高值。
: 最近换汤不换药，出了speaker的版本：
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: epi有两道题，14.19和15.1处理这类问题。
: 方法是不同的，
: 一个先将endpoint排序，另外用一个BST维护当前的最大高度，然后结束时就删除相应
: 的节点，这个感觉很难想，代码简洁一点。
: 另一个是mergesort。思路简单，代码要冗长一点。
: 个人感觉前者适用于应付stream，如果是静态数据应该mergesort就够了。
|
