一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2078|回复: 9
收起左侧

[算法题] 请教f家 task schedule题目follow up

[复制链接] |试试Instant~ |关注本帖
caffery24 发表于 2016-1-13 05:36:33 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
看见了面经里面的:
有一个task :  thread: 1, 2, 1, 1, 3, 4; 冷却时间: 2 time slot,scheduler应该是这样的:1, 2, _, 1, _, _, 3, 4,最后返回8
想请教下入锅不要求tread的顺序,即可以先执行3再执行1,怎么做???
163 发表于 2016-1-16 04:18:04 | 显示全部楼层
caffery24 发表于 2016-1-16 02:08
层主。。。求问下入锅每一次要挑可行的并且剩余次数最大的那一个。。。那不是每一个时间节点都要最大o(n) ...

你要用priority_queue
这样就是每个节点log(n)了。

当然如果按照原题那种,只考虑大写字母的话,每个节点即便用笨办法,撑死也就O(26)
回复 支持 1 反对 0

使用道具 举报

163 发表于 2016-1-13 07:25:11 | 显示全部楼层
到达一个空位后,挑当前这个空位可以选的那些任务里面余下任务数目最多的那个。
比如任务是AAABBBBBBBBBBBBCC,冷却时间是2
第一个位置先选B
接下来两个位置就都不能选B了,第二个就从A和C里面挑余下任务数最多的。以此类推。

这是个贪心法。请楼主尝试说明为什么能给出最优解。(个人认为完全说清楚还是需要一定水平的)
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2016-1-13 09:25:57 | 显示全部楼层
163 发表于 2016-1-13 07:25
到达一个空位后,挑当前这个空位可以选的那些任务里面余下任务数目最多的那个。
比如任务是AAABBBBBBBBBBB ...

哦哦,谢谢啦,就是先得统计下频率,然后每次找可以安排的频率最大的任务进行。。。感觉贪心有时候挺难说的
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2016-1-16 02:08:33 | 显示全部楼层
163 发表于 2016-1-13 07:25
到达一个空位后,挑当前这个空位可以选的那些任务里面余下任务数目最多的那个。
比如任务是AAABBBBBBBBBBB ...

层主。。。求问下入锅每一次要挑可行的并且剩余次数最大的那一个。。。那不是每一个时间节点都要最大o(n)time?
回复 支持 反对

使用道具 举报

Augustus 发表于 2016-1-16 02:34:20 | 显示全部楼层
用multiset吧。。。。
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2016-1-16 02:52:14 | 显示全部楼层
Augustus 发表于 2016-1-16 02:34
用multiset吧。。。。

用java 好像没这个。。。
回复 支持 反对

使用道具 举报

Augustus 发表于 2016-1-16 03:19:53 | 显示全部楼层
caffery24 发表于 2016-1-16 02:52
用java 好像没这个。。。

应该有类似的支持内部查询删除插入的数据结构吧。。。
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2016-1-16 03:22:59 | 显示全部楼层
Augustus 发表于 2016-1-16 03:19
应该有类似的支持内部查询删除插入的数据结构吧。。。

我的意思是,每次不是得拿剩余次数最多的,然后再看它是否现在可以做,所以有可能最坏情况要check所有的?
回复 支持 反对

使用道具 举报

frank11118 发表于 2016-2-25 12:18:39 | 显示全部楼层
請問原題目最佳解的時間複雜度是 O(n),空間複雜度是 O(# of type of task) 嗎? 謝謝!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 12:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表