leetcode 621. Task Scheduler
题目
给一些任务tasks需要尽快完成,但是有一个限制,相同任务必须间隔n个其他任务。
比如:
1 | Input: tasks = ["A","A","A","B","B","B"], n = 2 |
由于”A”是次数最多的任务,它会把任务序列分割成 A X X A X X A X X,因此每次迭代就是以次数最多的任务来分割,这样tasks完成时间最小。
方法一
1 | class Solution { |
时间复杂度O(n)
空间复杂度O(1)
方法二
普通情况
每次迭代,任务种类小于n+1的情况,需要idle来填充,可以发现最后的都是次数最多的任务,这种情况下,令次数最大的任务个数为p,次数最大的任务的次数为k,则结果为为(n+1)*(k-1) + p
1 | tasks = ["A","A","A","B","B","B"], n = 2 |
A B idle
A B idle
A B
n = 2, k = 3, p = 2, 结果(2+1)*(3-1)+2=8,因为这里A、B的次数相同所以p=2
1 | tasks = ["A","A","A","B","B","C"], n = 2 |
A B C
A B idle
A
n = 2, k = 3, p = 1, 结果(2+1)*(3-1)+1=7
特殊情况
当次数最多的任务A的次数n+1小于tasks数量, 也就是*A的间隔放不下所有tasks时
1 | tasks = ["A","A","A","B","B","C", "C", "D", "D", "F"], n = 2 |
A B C
A B C
D F A
D
n = 2, k = 3, p = 1, 结果(2+1)*(3-1)+1=7小于实际情况,这时候就需要
1 | class Solution { |
- 本文链接:https://dowob.cn/2019/02/08/leetcode-621-Task-Scheduler/
- 版权声明:本站所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处!