想了很久,请大家帮忙看看

昨天面试官问了一道编程题:
现在有三个打印机,假设每个打印机都是一样的。
然后现在有一个数组,数组里面存着大于零的整数,数组里存储的数字代表一个打印任务,数值是完成这个打印任务需要的时长。
请问该用怎么样的策略来分配任务给打印机,能使得完成所有任务的时间最短?


举个例子:
假设有任务:5,5,5,6,7,8,9
我们给每台打印机分配任务:
打印机A:5,5,5
打印机B:6,9
打印机C:7,8
这样完成所有任务的时间就是15,也就是最短的时间。
#面试题目#
全部评论
或者用dfs呢,直接暴力搜索
点赞 回复 分享
发布于 2020-09-13 14:56
这是np完全问题,没有最优解
点赞 回复 分享
发布于 2020-09-13 10:07
动态规划?最理想的最短时间就是每个打印机的工作时间是总时长的三分之一。先求最接近小余等于三分之一的情况,然后求解剩下的最接***分的情况。不过这样好像不方面求的具体方案啊。。
点赞 回复 分享
发布于 2020-09-13 00:23
贪心?
点赞 回复 分享
发布于 2020-09-12 23:10
二分最短时间?
点赞 回复 分享
发布于 2020-09-12 23:09
我当时的思路是将所有任务排序,从最大的开始分配,每次将任务分给目前任务最少的打印机,但是面试官说不对,能举出反例。当时没想出来反例是什么,现在发现确实有反例,就是描述中的例子
点赞 回复 分享
发布于 2020-09-12 22:58

相关推荐

不愿透露姓名的神秘牛友
07-24 13:32
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
今天 17:30
中南大学 Java
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务