20.12.10 leetcode621

标签:模拟   字符   n+1   自己的   max   etc   一个   次数   时间   

题目链接:https://leetcode-cn.com/problems/task-scheduler/

题意:给你一个大写字母字符串,每个字母表示一类任务,执行每个任务需要消耗一个单位时间,相同任务间必须间隔n,允许某个单位时间内空闲,求执行完所有任务的最小时间。

分析:这个题的题解很不错,值得一看,接下来用我自己的说法说一下。

方法1模拟:按照时间顺序一步步模拟,每一类任务维护两个值:1.下一个允许的时间最早为(初始都为1,若在时间j执行了该类任务,就将最早时间修改为j+n+1)2.该任务还有多少没执行。每次对于满足运行最早时间小于等于当前时间的所有任务,选择还没执行次数最多的。

方法2构造:一开始找出需执行次数最多(maxExec)的任务,假设从这个任务开始的话,最短时间为(maxExev-1)*(n+1)+1,如果执行次数为maxExec的任务有count(先假设count的数目小于n+1)的话,最短时间就为(maxExec-1)*(n+1)+count了,对于剩下的任务种类,将其插入空位中,插法是每段空位只差一个,因为他们的总数目是小于maxExec的,所以按这种插法肯定能够满足相距n,此时如果中间的空位够将剩余任务安排完,那么答案就是(maxExec-1)*(n+1)+count,如果不够的话,就在这n位的空位后面继续忘后面插,还是每段空位只插一个,这样答案是在|task|和(maxExec-1)*(n+1)+count中选较大值了。(对于count数目大于n+1的,答案直接就是|task|了)。

20.12.10 leetcode621

标签:模拟   字符   n+1   自己的   max   etc   一个   次数   时间   

原文地址:https://www.cnblogs.com/qingjiuling/p/14117731.html

版权声明:完美者 发表于 2020-12-16 11:57:47。
转载请注明:20.12.10 leetcode621 | 完美导航

暂无评论

暂无评论...