今年4月中的pd perm还有没批的吗 - 未名空间MITBBS历史存档

今年4月中的pd perm还有没批的吗# EB23 - 劳工卡

d*n2016-07-29 07:07

1 楼

是这个贴子里发出的
http://www.mitbbs.com/article_t/JobHunting/32569901.html
第二题是这样的：
n个Speaker，S1, S2, ...Sn
每个Speaker在不同的时间段有不同的音量如：
S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
...
请输出每个时间段及这个时间段内最大的音量
比如，只有S1和S2的话，输出就是
[1,2],vol=1, [2,5], vol=10, [5,6], vol = 1, [6,8], vol = 2, [8,12], vol = 8.
看了帖子后还是不明白O(nlog(n))是怎么解决的
有真正明白而且写过code的牛人能不能解释一下

n*r2016-07-29 07:07

2 楼

我有两个困惑
1。要发表但没有发表的文章（准备中的文章）应该列上去吗？
2. 一些小奖项要列进去吗？我不打算claim奖项，就是老三样。
谢谢。

D*72016-07-29 07:07

3 楼

Trackitt 上都批到5月中了 4月的大部分都批完了在dolstats上搜了自己的case
number 还是no record 有点着急了 audit现在大概晚多久通知

l*n2016-07-29 07:07

4 楼

每个时间段还有找最大的要求，应该会比O(nolgn)要稍大。
class Record {
int start;
int end;
int vol;
public Record(int s, int e, int vol) {
assert (s < e);
this.start = s;
this.end = e;
this.vol = vol;
}
}
class Point {
int time;
boolean isStart;
Record rec;
public Point(int time, boolean isStart, Record rec) {
this.time = time;
this.isStart = isStart;
this.rec = rec;
}
}
ArrayList loudestVol(Record[] varr) {
assert (varr != null);
ArrayList ol = new ArrayList();
if (varr.length == 0)
return ol;
Point[] parr = new Point[varr.length * 2];
for (int i = 0; i < varr.length; i++) {
parr[i * 2] = new Point(varr[i].start, true, varr[i]);
parr[i * 2 + 1] = new Point(varr[i].end, false, varr[i]);
}
// 起始点、终止点sorting
Arrays.sort(parr, new Comparator() {
public int compare(Point a, Point b) {
return a.time - b.time;
}
});
// max heap
PriorityQueue heap = new PriorityQueue(1,
new Comparator() {
public int compare(Record a, Record b) {
return b.vol - a.vol;
}
});
// 统计区间起始点
int start = parr[0].time;
heap.offer(parr[0].rec);
int i = 1;
// 开了多少个区间
int recOpened = 1;
while (i < parr.length) {
Point curr = parr[i++];
if (recOpened == 0) //开过的区间全部关闭
start = curr.time;
if (curr.time != start) {
ol.add(new Record(start, curr.time, heap.peek().vol));
start = curr.time; // 新的统计起始点
}
if (curr.isStart) {
heap.offer(curr.rec);
recOpened++;
} else {
heap.remove(curr.rec); // O(n) remove。自己写heap结构可以O(logn)
recOpened--;
}
}
return ol;
}

【在 d***n 的大作中提到】

: 是这个贴子里发出的
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

C*72016-07-29 07:07

5 楼

1.可以.但是没有正式发表的文章不要在scholarly article里面claim.
2.可以.但是不要单独在media report里面claim。

l*52016-07-29 07:07

6 楼

我三月的pd这周四才批下来……都有慢的……

s*x2016-07-29 07:07

7 楼

嗯，这个跟系列线段里找最多重复线段一个解法，就是起始点统一排序，然后扫描，碰
到起点处理新的区间，碰到终点，结束一个区间的处理。

n*r2016-07-29 07:07

8 楼

Thanks a lot.
Good luck to your application too.

【在 C********7 的大作中提到】

: 1.可以.但是没有正式发表的文章不要在scholarly article里面claim.
: 2.可以.但是不要单独在media report里面claim。

D*72016-07-29 07:07

9 楼

Cong! 希望能沾好运：）

【在 l*********5 的大作中提到】

: 我三月的pd这周四才批下来……都有慢的……

d*n2016-07-29 07:07

10 楼

不一样吧
不信你试着解一下
看能得出所要的答案么
这个确实是原贴说的skyline problem

【在 s**x 的大作中提到】

: 嗯，这个跟系列线段里找最多重复线段一个解法，就是起始点统一排序，然后扫描，碰
: 到起点处理新的区间，碰到终点，结束一个区间的处理。

s*72016-07-29 07:07

11 楼

跑去DOL上统计了我们公司的perm数据。看了大概看了30个数据。貌似大多是80-120天。
不知道这个速度和location, company，JD有关系不。也希望我自己的顺利批下来。

l*o2016-07-29 07:07

12 楼

Sdlx 排序后的code细节看这里
https://sites.google.com/site/yantchenacm/code/uva-volume-1/105
目测是可以的
回头在电脑上试试看

★ 发自iPhone App: ChineseWeb 7.8

【在 d***n 的大作中提到】

: 不一样吧
: 不信你试着解一下
: 看能得出所要的答案么
: 这个确实是原贴说的skyline problem

l*o2016-07-29 07:07

13 楼

原帖 26 楼 novice 的算法是work的，那个算法跟上面的算法，各有优劣。都不错。

★ 发自iPhone App: ChineseWeb 7.8

【在 d***n 的大作中提到】

: 不一样吧
: 不信你试着解一下
: 看能得出所要的答案么
: 这个确实是原贴说的skyline problem

w*e2016-07-29 07:07

14 楼

显然不work啊，当遇到end的时候，需要把该end所属区间的volume从heap里删掉，如果
当前的volume不是最大的话，怎么从heap里删掉？？
novice的就解法是这样的：
“
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。
”

【在 l**********o 的大作中提到】

: 原帖 26 楼 novice 的算法是work的，那个算法跟上面的算法，各有优劣。都不错。
:
: ★ 发自iPhone App: ChineseWeb 7.8

s*x2016-07-29 07:07

15 楼

you are right.
see update #26 in http://www.mitbbs.com/article_t1/JobHunting/32569901_0_2.html.
initially I thought they want the volume sum.
for volume max, looks like you need to maintain a max heap or a BST when you
are scanning the endpoints.
the problem for max heap is that it is a little tricky to remove the
endpoint element from the heap.
For balanced BST, you can find the max and remove an element with O(logn),
so not bad.

【在 d***n 的大作中提到】

: 不一样吧
: 不信你试着解一下
: 看能得出所要的答案么
: 这个确实是原贴说的skyline problem

w*e2016-07-29 07:07

16 楼

这道题目非常复杂，首先能想到n*log(n)的算法就不简单，即使想到了，能够在面试的
压力下把逻辑coding出来也非常的难。我感觉电面中，问到这种题目而且要coding的，
如果从没有见过，基本就是不让你过。感觉这种题目适合onsite用。
在知道算法后，我大概花了一些时间，写了如下的代码，基本思路就是楼上讨论的。
1. 首先把所有的interval的起点和终点存进一个vector,并且sort
struct timePoint {
int point;
bool startORend;
int vol;
timePoint(int p, bool s, int v): point(p), startORend(s), vol(v) {}
};
2. 建立一个multiset用来存储还没有结束的volume，同时可以用来判断某个时间段是
否被输入的interval cover了。
3. 然后扫描vector开始建立输出的vector：
1）如果碰到start的点，先检查multiset是否为空，如果是，就是insert当前point的
volume；如果不为空，就比较当前volume与multiset里的最大值，如果当前的volume大
，那就创建一个interval，push到输出的vector里去；否则，新的时间段仍可以被前一
段cover
2）如果碰到end的点，先erase当前的volume，然后判断multiset是否为空，如果为空
，创建一个interval，push到输出的vector；如果不为空，检查multiset里的最大值是
否比当前的volume要小，如果是，创建一个interval，否则（最多是等于），就不创建。
代码如下，感觉肯定有bug，欢迎大家指正
struct timePoint {
int point;
bool startORend;
int vol;
timePoint(int p, bool s, int v): point(p), startORend(s), vol(v) {}
};
struct Interval {
int start, end;
int vol;
Interval(int s, int e, int v): start(s), end(e), vol(v) {}
};
static bool compare(timePoint &p1, timePoint &p2) {return p1.pointvector findMaxVol(vector > &intv) {
vector ret;
if(intv.size()<2) return intv;
vector p;
for(int i=0; ip.push_back(timePoint(intv.start, 0, invl.vol));
p.push_back(timePoint(intv.end, 1, invl.vol));
}
sort(p.begin(), p.end(), compare);
multiset mp;
timePoint prev(p[0].point, 0, p[0].vol);
mp.insert(p[0].vol);
for(int i=1; iif(p.startORend==0) {
if(mp.empty()==0) {
int vol = *(--mp.end());
if(p[i].vol>vol) {
ret.push_back(Inverval(prev.point, p[i].point, vol));
prev = p[i];
}
} else prev = p[i].point; //which means that the time before
this is not covered by the input
mp.insert(p[i].vol);
}
else {
mp.erase(prev.vol);
if(mp.empty()==0) { //some time space is not covered by the
input
int vol = *(--mp.end());
if(volpoint, prev.vol));
prev_start = p[i].point;
} else ret.push_back(Interval(prev.point, p[i].point, prev.vol));
}
}
return ret;
}

you

【在 s**x 的大作中提到】

: you are right.
: see update #26 in http://www.mitbbs.com/article_t1/JobHunting/32569901_0_2.html.
: initially I thought they want the volume sum.
: for volume max, looks like you need to maintain a max heap or a BST when you
: are scanning the endpoints.
: the problem for max heap is that it is a little tricky to remove the
: endpoint element from the heap.
: For balanced BST, you can find the max and remove an element with O(logn),
: so not bad.

l*n2016-07-29 07:07

17 楼

heap的内容是可以删的。java library的heap 任意节点的删除是O(n)，但是自己写
heap可以做到O(logn)的删除。

【在 w*******e 的大作中提到】

: 显然不work啊，当遇到end的时候，需要把该end所属区间的volume从heap里删掉，如果
: 当前的volume不是最大的话，怎么从heap里删掉？？
: novice的就解法是这样的：
: “
: Skyline 的解法貌似是（没记错的话）：
: 把所有的turning points 放在一起，根据coordination从小到大sort 。
: struct turnpoint {
: int ptr; //coordinate;
: bool startOrEnd;
: int volume

K*g2016-07-29 07:07

18 楼

how？

★ 发自iPhone App: ChineseWeb 7.8

【在 l*n 的大作中提到】

: heap的内容是可以删的。java library的heap 任意节点的删除是O(n)，但是自己写
: heap可以做到O(logn)的删除。

l*n2016-07-29 07:07

19 楼

建一个map来记录heap中节点的index，然后在heap的sift操作中节点互换时更新map的
内容。最后删除heap节点时，把最后一个节点放到删除的位置然后做一次sift操作。

【在 K******g 的大作中提到】

: how？
:
: ★ 发自iPhone App: ChineseWeb 7.8

n*f2016-07-29 07:07

20 楼

把每条线段拆成进、出两个事件，排序后扫一遍。维护一个可以删点的大顶堆，遇到进
事件就insert，遇到出事件就delete，每两个事件之间堆的top就是这个时段的最大值。
对于delete操作，一种偷懒的做法是先不删它，每次取top的时候判断一下top元素是否
已经被删掉了，如果是就pop。这种方法是不会降低worst case的复杂度的。正规的方
法，也就是要删中间节点，就需要多维护每个节点的编号，以及每个编号的位置，每次
堆sink和swim都需要做相应的修改。删除时把最后一个结点移到被删的节点位置，然后
sink或swim。

l*62016-07-29 07:07

21 楼

这一题跟skyline 不同，是个变形体吧。两个speaker ，各自事件已经排序且没有
重叠，相互事件可以重叠。
用于记volumn的maxHeap 最多有两个元素。用于记录time event 的minHeap 同样
不用把两个speaker的事件merge再sort，keep一个size为2 的 timeevent 的minheap，
一开始把两个speaker的start event放进time heap。然后开始pop timeevent heap.
pop出start event的时候，往volumn heap里面push 这个start event 对应的volumn
同时把这个start event对应的end event push进time heap。update result
pop出end event 的时候，把volumn heap里面对应的volumn pop出来，把这个
speaker对应的下一个start event push进time event。 update result
每个 event push pop 各一次
heap size ， volumn heap 和time heap 最多为2 （2个speaker）
复杂度O(n)

c*p2016-07-29 07:07

22 楼

mark

d*n2016-07-29 07:07

23 楼

是这个贴子里发出的
http://www.mitbbs.com/article_t/JobHunting/32569901.html
第二题是这样的：
n个Speaker，S1, S2, ...Sn
每个Speaker在不同的时间段有不同的音量如：
S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
...
请输出每个时间段及这个时间段内最大的音量
比如，只有S1和S2的话，输出就是
[1,2],vol=1, [2,5], vol=10, [5,6], vol = 1, [6,8], vol = 2, [8,12], vol = 8.
看了帖子后还是不明白O(nlog(n))是怎么解决的
有真正明白而且写过code的牛人能不能解释一下

l*n2016-07-29 07:07

24 楼

class Record {
int start;
int end;
int vol;
public Record(int s, int e, int vol) {
assert (s < e);
this.start = s;
this.end = e;
this.vol = vol;
}
}
class Point {
int time;
boolean isStart;
Record rec;
public Point(int time, boolean isStart, Record rec) {
this.time = time;
this.isStart = isStart;
this.rec = rec;
}
}
ArrayList loudestVol(Record[] varr) {
assert (varr != null);
ArrayList ol = new ArrayList();
if (varr.length == 0)
return ol;
Point[] parr = new Point[varr.length * 2];
for (int i = 0; i < varr.length; i++) {
parr[i * 2] = new Point(varr[i].start, true, varr[i]);
parr[i * 2 + 1] = new Point(varr[i].end, false, varr[i]);
}
// 起始点、终止点sorting
Arrays.sort(parr, new Comparator() {
public int compare(Point a, Point b) {
return a.time - b.time;
}
});
// max heap
PriorityQueue heap = new PriorityQueue(1,
new Comparator() {
public int compare(Record a, Record b) {
return b.vol - a.vol;
}
});
// 统计区间起始点
int start = parr[0].time;
heap.offer(parr[0].rec);
int i = 1;
// 开了多少个区间
int recOpened = 1;
while (i < parr.length) {
Point curr = parr[i++];
if (recOpened == 0) //开过的区间全部关闭
start = curr.time;
if (curr.time != start) {
ol.add(new Record(start, curr.time, heap.peek().vol));
start = curr.time; // 新的统计起始点
}
if (curr.isStart) {
heap.offer(curr.rec);
recOpened++;
} else {
heap.remove(curr.rec); // O(n) remove。自己写heap结构可以O(logn)
recOpened--;
}
}
return ol;
}

【在 d***n 的大作中提到】

: 是这个贴子里发出的
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

s*x2016-07-29 07:07

25 楼

嗯，这个跟系列线段里找最多重复线段一个解法，就是起始点统一排序，然后扫描，碰
到起点处理新的区间，碰到终点，结束一个区间的处理。

d*n2016-07-29 07:07

26 楼

不一样吧
不信你试着解一下
看能得出所要的答案么
这个确实是原贴说的skyline problem

【在 s**x 的大作中提到】

: 嗯，这个跟系列线段里找最多重复线段一个解法，就是起始点统一排序，然后扫描，碰
: 到起点处理新的区间，碰到终点，结束一个区间的处理。

l*o2016-07-29 07:07

27 楼

Sdlx 排序后的code细节看这里
https://sites.google.com/site/yantchenacm/code/uva-volume-1/105
目测是可以的
回头在电脑上试试看

★ 发自iPhone App: ChineseWeb 7.8

【在 d***n 的大作中提到】

: 不一样吧
: 不信你试着解一下
: 看能得出所要的答案么
: 这个确实是原贴说的skyline problem

l*o2016-07-29 07:07

28 楼

原帖 26 楼 novice 的算法是work的，那个算法跟上面的算法，各有优劣。都不错。

★ 发自iPhone App: ChineseWeb 7.8

【在 d***n 的大作中提到】

: 不一样吧
: 不信你试着解一下
: 看能得出所要的答案么
: 这个确实是原贴说的skyline problem

w*e2016-07-29 07:07

29 楼

显然不work啊，当遇到end的时候，需要把该end所属区间的volume从heap里删掉，如果
当前的volume不是最大的话，怎么从heap里删掉？？
novice的就解法是这样的：
“
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。
”

【在 l**********o 的大作中提到】

: 原帖 26 楼 novice 的算法是work的，那个算法跟上面的算法，各有优劣。都不错。
:
: ★ 发自iPhone App: ChineseWeb 7.8

s*x2016-07-29 07:07

30 楼

you are right.
see update #26 in http://www.mitbbs.com/article_t1/JobHunting/32569901_0_2.html.
initially I thought they want the volume sum.
for volume max, looks like you need to maintain a max heap or a BST when you
are scanning the endpoints.
the problem for max heap is that it is a little tricky to remove the
endpoint element from the heap.
For balanced BST, you can find the max and remove an element with O(logn),
so not bad.

【在 d***n 的大作中提到】

: 不一样吧
: 不信你试着解一下
: 看能得出所要的答案么
: 这个确实是原贴说的skyline problem

w*e2016-07-29 07:07

31 楼

这道题目非常复杂，首先能想到n*log(n)的算法就不简单，即使想到了，能够在面试的
压力下把逻辑coding出来也非常的难。我感觉电面中，问到这种题目而且要coding的，
如果从没有见过，基本就是不让你过。感觉这种题目适合onsite用。
在知道算法后，我大概花了一些时间，写了如下的代码，基本思路就是楼上讨论的。
1. 首先把所有的interval的起点和终点存进一个vector,并且sort
struct timePoint {
int point;
bool startORend;
int vol;
timePoint(int p, bool s, int v): point(p), startORend(s), vol(v) {}
};
2. 建立一个multiset用来存储还没有结束的volume，同时可以用来判断某个时间段是
否被输入的interval cover了。
3. 然后扫描vector开始建立输出的vector：
1）如果碰到start的点，先检查multiset是否为空，如果是，就是insert当前point的
volume；如果不为空，就比较当前volume与multiset里的最大值，如果当前的volume大
，那就创建一个interval，push到输出的vector里去；否则，新的时间段仍可以被前一
段cover
2）如果碰到end的点，先erase当前的volume，然后判断multiset是否为空，如果为空
，创建一个interval，push到输出的vector；如果不为空，检查multiset里的最大值是
否比当前的volume要小，如果是，创建一个interval，否则（最多是等于），就不创建。
代码如下，感觉肯定有bug，欢迎大家指正
struct timePoint {
int point;
bool startORend;
int vol;
timePoint(int p, bool s, int v): point(p), startORend(s), vol(v) {}
};
struct Interval {
int start, end;
int vol;
Interval(int s, int e, int v): start(s), end(e), vol(v) {}
};
static bool compare(timePoint &p1, timePoint &p2) {return p1.pointvector findMaxVol(vector > &intv) {
vector ret;
if(intv.size()<2) return intv;
vector p;
for(int i=0; ip.push_back(timePoint(intv.start, 0, invl.vol));
p.push_back(timePoint(intv.end, 1, invl.vol));
}
sort(p.begin(), p.end(), compare);
multiset mp;
timePoint prev(p[0].point, 0, p[0].vol);
mp.insert(p[0].vol);
for(int i=1; iif(p.startORend==0) {
if(mp.empty()==0) {
int vol = *(--mp.end());
if(p[i].vol>vol) {
ret.push_back(Inverval(prev.point, p[i].point, vol));
prev = p[i];
}
} else prev = p[i].point; //which means that the time before
this is not covered by the input
mp.insert(p[i].vol);
}
else {
mp.erase(prev.vol);
if(mp.empty()==0) { //some time space is not covered by the
input
int vol = *(--mp.end());
if(volpoint, prev.vol));
prev_start = p[i].point;
} else ret.push_back(Interval(prev.point, p[i].point, prev.vol));
}
}
return ret;
}

you

【在 s**x 的大作中提到】

: you are right.
: see update #26 in http://www.mitbbs.com/article_t1/JobHunting/32569901_0_2.html.
: initially I thought they want the volume sum.
: for volume max, looks like you need to maintain a max heap or a BST when you
: are scanning the endpoints.
: the problem for max heap is that it is a little tricky to remove the
: endpoint element from the heap.
: For balanced BST, you can find the max and remove an element with O(logn),
: so not bad.

l*n2016-07-29 07:07

32 楼

heap的内容是可以删的。java library的heap 任意节点的删除是O(n)，但是自己写
heap可以做到O(logn)的删除。

【在 w*******e 的大作中提到】

: 显然不work啊，当遇到end的时候，需要把该end所属区间的volume从heap里删掉，如果
: 当前的volume不是最大的话，怎么从heap里删掉？？
: novice的就解法是这样的：
: “
: Skyline 的解法貌似是（没记错的话）：
: 把所有的turning points 放在一起，根据coordination从小到大sort 。
: struct turnpoint {
: int ptr; //coordinate;
: bool startOrEnd;
: int volume

K*g2016-07-29 07:07

33 楼

how？

★ 发自iPhone App: ChineseWeb 7.8

【在 l*n 的大作中提到】

: heap的内容是可以删的。java library的heap 任意节点的删除是O(n)，但是自己写
: heap可以做到O(logn)的删除。

l*n2016-07-29 07:07

34 楼

建一个map来记录heap中节点的index，然后在heap的sift操作中节点互换时更新map的
内容。最后删除heap节点时，把最后一个节点放到删除的位置然后做一次sift操作。

【在 K******g 的大作中提到】

: how？
:
: ★ 发自iPhone App: ChineseWeb 7.8

n*f2016-07-29 07:07

35 楼

把每条线段拆成进、出两个事件，排序后扫一遍。维护一个可以删点的大顶堆，遇到进
事件就insert，遇到出事件就delete，每两个事件之间堆的top就是这个时段的最大值。
对于delete操作，一种偷懒的做法是先不删它，每次取top的时候判断一下top元素是否
已经被删掉了，如果是就pop。这种方法是不会降低worst case的复杂度的。正规的方
法，也就是要删中间节点，就需要多维护每个节点的编号，以及每个编号的位置，每次
堆sink和swim都需要做相应的修改。删除时把最后一个结点移到被删的节点位置，然后
sink或swim。

l*62016-07-29 07:07

36 楼

这一题跟skyline 不同，是个变形体吧。两个speaker ，各自事件已经排序且没有
重叠，相互事件可以重叠。
用于记volumn的maxHeap 最多有两个元素。用于记录time event 的minHeap 同样
不用把两个speaker的事件merge再sort，keep一个size为2 的 timeevent 的minheap，
一开始把两个speaker的start event放进time heap。然后开始pop timeevent heap.
pop出start event的时候，往volumn heap里面push 这个start event 对应的volumn
同时把这个start event对应的end event push进time heap。update result
pop出end event 的时候，把volumn heap里面对应的volumn pop出来，把这个
speaker对应的下一个start event push进time event。 update result
每个 event push pop 各一次
heap size ， volumn heap 和time heap 最多为2 （2个speaker）
复杂度O(n)

c*p2016-07-29 07:07

37 楼

mark

b*a2016-07-29 07:07

38 楼

难道不是merge intervals

G*m2016-07-29 07:07

39 楼

店面搞这题估计就是讨论一下思路吧？

【在 d***n 的大作中提到】

: 是这个贴子里发出的
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

c*n2016-07-29 07:07

40 楼

就是skyline 换个说法, recursively merge 2 skylines NlogN

【在 d***n 的大作中提到】

: 是这个贴子里发出的
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

A*e2016-07-29 07:07

41 楼

按端点排序就行了。进左端点加音量，右端点减。

【在 d***n 的大作中提到】

: 是这个贴子里发出的
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是

A*e2016-07-29 07:07

42 楼

原来音量不能叠加？古怪。一个喇叭和两个喇叭的音量显然不一样啊。

【在 d***n 的大作中提到】

: 是这个贴子里发出的
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: 第二题是这样的：
: n个Speaker，S1, S2, ...Sn
: 每个Speaker在不同的时间段有不同的音量如：
: S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
: S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
: ...
: 请输出每个时间段及这个时间段内最大的音量
: 比如，只有S1和S2的话，输出就是