o********d
发帖数: 22 | 1 given an array of processes, each has start, end, load
find the process with max load at each time step and print it
题目都没有看太明白，特别是“at each time step”， 大家伙帮忙看看什么意思阿，
面经链接 http://www.amoduo.com/article/view/1004239.html | x****g
发帖数: 1512 | 2 我的理解是给出任意时间点，最繁忙的进程。
假设数每个数据为A{start,end,load}
举个简单例子:
A{0, 3, 1} A{1,4} 2.
那么结果就是:
{0,1}最大1
{1,4}最大2
其它时间没有.
貌似Nlog(N)的算法?
按开始时间排序. Nlog(N)
A1.....An
如果:
A1.end <= A2.start 输出A1就行.
否者
A1.end > A2.start.
输出A1.start A2.start A1 weight
同时更新 A2 weight = max (A1,A2) weight.
继续下一个,直到结束. | x****g
发帖数: 1512 | 3 回想了一下,有错误,需要改一下.
当A1.end > A2.start的时候只更新A2,回导致信息丢失.
极端如A1.end cover了全部.
只更新A2的话,如果A2无法级联往后的话,相当于信息丢失了.
所以这步更新不对.
应该按A1.end在排序的start里找到最后一个Ak.start < A1.end. log(N)
完了从A2->Ak的weight都得更新成max(A1,Ai).
输出方法不变.
感觉不是很优化,不知道有更好的法子没,继续思考,呵呵.
【在 x****g 的大作中提到】
: 我的理解是给出任意时间点，最繁忙的进程。
: 假设数每个数据为A{start,end,load}
: 举个简单例子:
: A{0, 3, 1} A{1,4} 2.
: 那么结果就是:
: {0,1}最大1
: {1,4}最大2
: 其它时间没有.
: 貌似Nlog(N)的算法?
: 按开始时间排序. Nlog(N)
| m**********g
发帖数: 153 | 4 it looks like the skyline problem based on the description:
find "the process" with max load at each time step |
|
