请教f家 task schedule题目follow up

看见了面经里面的：
有一个task :  thread: 1, 2, 1, 1, 3, 4; 冷却时间: 2 time slot，scheduler应该是这样的：1, 2, _, 1, _, _, 3, 4，最后返回8
想请教下入锅不要求tread的顺序，即可以先执行3再执行1，怎么做？？？

caffery24 发表于 2016-1-16 02:08
层主。。。求问下入锅每一次要挑可行的并且剩余次数最大的那一个。。。那不是每一个时间节点都要最大o(n) ...

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

当然如果按照原题那种，只考虑大写字母的话，每个节点即便用笨办法，撑死也就O(26)

到达一个空位后，挑当前这个空位可以选的那些任务里面余下任务数目最多的那个。
比如任务是AAABBBBBBBBBBBBCC，冷却时间是2
第一个位置先选B
接下来两个位置就都不能选B了，第二个就从A和C里面挑余下任务数最多的。以此类推。

这是个贪心法。请楼主尝试说明为什么能给出最优解。（个人认为完全说清楚还是需要一定水平的）

163 发表于 2016-1-13 07:25
到达一个空位后，挑当前这个空位可以选的那些任务里面余下任务数目最多的那个。
比如任务是AAABBBBBBBBBBB ...

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

163 发表于 2016-1-13 07:25
到达一个空位后，挑当前这个空位可以选的那些任务里面余下任务数目最多的那个。
比如任务是AAABBBBBBBBBBB ...

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

用multiset吧。。。。

Augustus 发表于 2016-1-16 02:34
用multiset吧。。。。

用java 好像没这个。。。

caffery24 发表于 2016-1-16 02:52
用java 好像没这个。。。

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

Augustus 发表于 2016-1-16 03:19
应该有类似的支持内部查询删除插入的数据结构吧。。。

我的意思是，每次不是得拿剩余次数最多的，然后再看它是否现在可以做，所以有可能最坏情况要check所有的？

請問原題目最佳解的時間複雜度是 O(n)，空間複雜度是 O(# of type of task) 嗎？ 謝謝!