TaskScheduler

621. Task Scheduler

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.

输入是一组任务, 和一个冷却的时间$n$. 两个相同任务之间的至少要冷却$n$. 要求返回执行完所有任务所需要最少的时间.

Example 1:

tasks = [A, A, A, B, B, B] n = 2
return: 8

因为使用时间最少的执行顺序是 A->B->idel->A->B->idel->A->B

思路

明确的一点是, 如果只有一种任务, 他至少需要多少时间?

• 任务的个数 + 空闲时间

空闲时间怎么算?

• 任务个数 * 空闲时间 - 空闲时间.
• 例如 tasks = [A, A, A], n = 1, 最少需要$3\times1-1$的空闲时间. 所以要完成这个任务, 最少需要$3 + 2 = 5$

有了这个认识, 我们可以把一组任务中的每种任务的个数统计出来, 确定了个数最多的那个种类的最少执行时间, 然后将剩下的任务安插在其中.

例如
tasks = [A, A, A, B, B, B]
先安排A, 得出A->idel->idel->A->idel->idel->A
然后再安排B, 得出A->B->idel->A->B->idel->A->B

Code

def leastIntervals(tasks, n):
    helper = [0] * 128
    for x in tasks:
        helper[ord(x)] += 1
    
    helper = sorted(helper, reverse=True)
    res = helper[0] * (n+1)-n
    for i in range(1, len(helper)):
        if helper[i] == helper[0]:
            res += 1
        else:
            break
    return max(res, sum(helper))