脸二次店面

因为第一次店面on border，又加了一次店面，直接跪了
题目：
有n个job, with id 1-n。每个job的prerequisite job id都给出来了，只有当这个jo

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

是一样的，所以导致这里当k个worker中的一个任务结束的时候马上就可以开始下一个了。没太想明白怎么用那个题的方法来做这个...

匿名用户 发表于 2020-07-27 16:16:01
感觉硬BF都不是很容易....(是我太弱鸡了..)

每空出一个worker试所以可行任务为下一个，DFS simulation所有可能性。每次完成所有任务以后min一下完成时间？不过不知道有没有更优

补充内容 (2020-7-28 08:07):
taskqueue 可以用priority queue来模拟，从最快要完成的开始抽，mark complete，然后加上下一个你要试的task时间，放回去

第一问也不是很简单呀。想清楚了，代码写出来也蛮长的吧。

topology sorting的过程中，维护一个map
map<int, set<int>>,   维护每个节点所有父节点完成需要的时间，某个节点入度为0的时候，需要修改它所有后继节点，把完成这个节点所需要的时间insert到子节点的这个set里。节点入度为0的时候，从自己的这个set取max， 加上自己的时间，作为最终完成这个节点需要的时间。

distantstar 发表于 2020-7-28 06:52
面试给这种题不地道吧。。。

补系统设计的时候知道optimal task scheduling 是NP problem. 所以硬brute fo ...

感觉硬BF都不是很容易....(是我太弱鸡了..)

面试给这种题不地道吧。。。

补系统设计的时候知道optimal task scheduling 是NP problem. 所以硬brute force。。。也是可以的吧

这个整数规划是NP问题。。。

这道题不太好想，求大神给个参考答案

楼主是e几呀

这种题不知道要考到什么程度，估计能说出来这个是0-1规划应该可以获取点印象分吧

同求解答

你这个flowup有点难啊，flowup答不上来就挂了？