拼多多笔试第三题有问题?

测试用例
4 3
1 4 5 1
1 2
1 3
3 4
示意图如下,圆形内表示该任务的运行时间。

一共有三种情况。
情况一:1 3 4 2。总等待时间:1*4+5*3+1*2+4*1=25
情况二:1 2 3 4。总等待时间:1*4+4*3+5*2+1*1=27
情况三:1 3 2 4。总等待时间:1*4+5*3+4*2+1*1=28
情况一用时最少。但是我用了牛客上大佬们的代码,有的编译不过,有的运行答案是情况二。
这个题我第一感觉也是拓扑排序加堆,但是做出来的结果是情况二,而不是情况一。
请问这个题思路到底是什么样的?或者这个用例有什么错误的地方吗?
#拼多多##笔试题目#
全部评论
贪心,每次选入度为0的时间最短的活动执行,再更新入度
点赞 回复 分享
发布于 2019-07-29 13:19
时间算错了,好像要算的是平均等待时间,每个任务的等待实践=任务完成时间-最开始的开始时间
点赞 回复 分享
发布于 2019-07-29 13:49
支持楼主!
点赞 回复 分享
发布于 2019-07-29 13:57
震惊!大牛都做错的笔试题!难道?
点赞 回复 分享
发布于 2019-07-29 13:58
你分析的应该是对的,这个笔试第二、三题测试样例都有问题
点赞 回复 分享
发布于 2019-07-29 14:09
觉得贪心不能全局最优
点赞 回复 分享
发布于 2019-07-29 14:09
画个甘特图看起来清晰点,时间没算错。。。
点赞 回复 分享
发布于 2019-07-29 14:49
楼主说的对。我昨天压根没做出来,看了其他大佬的优先队列觉得有道理但是少考虑了特殊情况。这次的样例太水了,想的全面反而浪费时间。
点赞 回复 分享
发布于 2019-07-29 15:00
我觉得可能是因为题目是以  一个分布式任务执行平台  为背景来给测试样例的,所以,我觉得楼主举的这个反例貌似就不存在了, reduce过程应该不具有这样的反例吧(个人猜测)
点赞 回复 分享
发布于 2019-07-29 15:31

相关推荐

评论
6
8
分享

创作者周榜

更多
牛客网
牛客企业服务