问一道G家题

laiguojiuhao 发表于 2017-1-14 04:32
我是看到原帖作者是每次做最长时间的工作，既然他拿了offer我就假设他没问题；感觉有个条件可能，要不然 ...

分析的很有道理啊。。 这么一想这题好难啊。 那按照你这么思路， 有一个general的最佳策略么，我是说选工作的策略

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

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

laiguojiuhao 发表于 2017-1-14 05:52
没有。。。不过感觉似乎有一点道理，就是如果工人数固定，那可以用贪心从最大的开始安排；如果之后不再造 ...

感觉只能暴力做。。。而且比原先假想的暴力还要再多一层（遍历job的顺序。。。）

首先二分查找要多少个人
然后问题变成n个job，k个人，怎么分配最快完成。这个问题有办法解吗？

fengyang0317 发表于 2017-1-14 07:20
首先二分查找要多少个人
然后问题变成n个job，k个人，怎么分配最快完成。这个问题有办法解吗？

二分查找要多少个人是什么意思？

np hard问题吧，比如简化问题，有k个人n个job分配，这个简化都的问题就是NP hard..感觉没啥方法去做

有点不明白，同一个任务是只能由一个工人做还是可以多个工人并行做呢？

小A要当码农 发表于 2017-1-14 07:25
二分查找要多少个人是什么意思？

想简化成16楼说的问题。

最后总共用了k个人，k从1到n变化，我猜用的时间是先减少后增加，也可能只增加或者只减少。

不知道这样猜成立不成立。

如果成立，而且16楼说的问题可以解，就可以用三分来确定k。

zxj1987 发表于 2017-1-14 08:41
np hard问题吧，比如简化问题，有k个人n个job分配，这个简化都的问题就是NP hard..感觉没啥方法去做

01背包就是NP的，如果总的重量不是太大，用动态规划也能解。

这个job分配的问题也有希望能解吧

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

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