问一道G家题

有一堆任务需要完成，已知各个任务需要的不同的时间以及训练一个工人需要的时间，

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

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

这题我知道大概可以用DFS遍历每次工人是选训练新工人或者做任务，但是不太会covert成code，跟大牛求下思路

小A要当码农 发表于 2017-1-14 04:52
分析的很有道理啊。。 这么一想这题好难啊。 那按照你这么思路， 有一个general的最佳策略么，我是说选工 ...

没有。。。不过感觉似乎有一点道理，就是如果工人数固定，那可以用贪心从最大的开始安排；如果之后不再造人，这就是最优的；如果之后又造了人，那么根据我们的递归算法肯定会有一个分支是先造了同样数量的人然后开始贪心地安排工作，似乎能够cover到。比如我之前的长中短的例子，那么会有一个分支先造人，然后长中，中的完了再短，总共造一个人的情况下是最优的。
证明不会

laiguojiuhao 发表于 2017-1-10 07:47
每个工作应该只能一个做，搜索的上限是工人数量等于待完成的工作数量吧，再多没意义；简单的模拟可以设计一 ...

刚刚又想了一下这个题， 思路和你这个是一样的。 假设原帖作者说的每次挑选工作优先挑时间最长的话， 还需要维护一个关于job的max heap。 这样的话似乎可以根据当前闲置工人数目和当天剩余工作数目（因为挑选策略的原因，每次我们遇到还剩N个工作的case，这N个工作一定是一样的（最短的N个））做memo...

小A要当码农 发表于 2017-2-2 02:57
这个思路可行，但是只能是暴力便利枚举把？ 没有办法二分枚举把？

我有些问题，可能是我题意没理解对
1. 如果一个员工在在造人，其他的员工难道都等着么？
2. 如果几个员工同时在干活，第一个干完活的员工在其他员工干完活之前也等着么？
感觉你们的暴力枚举和DP的做法都是假设手快的员工busy wait 其他员工，然而正常情况下这个员工不是应该开始做下一个活了么？

不过如果题目是这样的话就太复杂了，我完全没有思路。

这题的搜索空间是无限的吧，关注一下

感觉工人每次单独选择工作还是造人 这样算法复杂度会很高 而且工人先工作 再造人的效率 显然是低于先造人再工作的效率的。我觉得这么做好一些，假设需要工人的数量为k 然后计算在k个工人下 完成所有任务需要的时间… 在最优的工人数量上下界中枚举 然后找到最优解。 最优工人数量的下界就设为0吧 上界应该就是 假如我只负责造人 工人只负责工作，在这个情况下的工人最优解。

可以用dp吧

有一个问题，同一个任务可以由不同工人同时做吗？还是说一个任务只能由一个工人做？

不同的工人可以并行地处理任务  

是处理同一个任务吗？ 还是不同的任务？

一个任务可以同时被2个工人做吗？ 我估计不可以吧 否则这题很复杂

最优解问题可以转移成DP 问题。

每个工作应该只能一个做，搜索的上限是工人数量等于待完成的工作数量吧，再多没意义；简单的模拟可以设计一个工人类，有三个状态，idle，造人，做事，然后工人有一个下一次空闲开始的时刻，用这个时刻作为工人min heap的key，递归的同时维护一个当前时间；pop出一个工人，判断其状态，根据当前时间决定总用时，有点像shortest job first schedule；可以用剩余的工作数量和当前工人数量做memoization；

laiguojiuhao 发表于 2017-1-10 07:47
每个工作应该只能一个做，搜索的上限是工人数量等于待完成的工作数量吧，再多没意义；简单的模拟可以设计一 ...

记忆画搜索似乎可行。这样就是O(N^2)复杂度， N是job的数目。 但是有个问题，这个题怎么说明总时间和做job的顺序无关呢？

小A要当码农 发表于 2017-1-14 04:21
记忆画搜索似乎可行。这样就是O(N^2)复杂度， N是job的数目。 但是有个问题，这个题怎么说明总时间和做jo ...

我是看到原帖作者是每次做最长时间的工作，既然他拿了offer我就假设他没问题；感觉有个条件可能，要不然确实可能和顺序有关系，比如三个工作时间，短，中，长
1.一开始一个人，做长的然后造人（我特么好想笑啊），然后做中和短，时间是 长+造人+中
2.如果先短，然后造人，然后长，时间是长+造人+短，更优