LeetCode0621.任务调度器 Go语言AC笔记

时间复杂度：O(n)

解题思路

其实该题更像是一道数学题。

由于执行每个相同任务都需要间隔n个时间片，所以执行次数最多的那个任务决定了总的时间，至少为“（最大执行次数-1）*（n+1）+1”，“最大执行次数-1”是最大执行次数任务需要间隔几次，“n+1”是分隔相同任务的宽度，最后的1是最后执行的那个任务。

按照此规律可以进行扩展，如果最大执行次数任务有两个呢？有三个、四个、五个呢？那么最小执行时间就应该是“（最大执行次数-1）*（n+1）+最大执行次数的任务数”，当然该式满足的前提是最大执行次数的任务数不大于n+1，否则会“溢出”。

溢出时对应于什么情况呢？我们不能在上面计算的最小时间内执行完所有任务，需要再分配时间执行未分配好的任务，所以此时最小执行时间就应该是需要执行的任务总数而不是上面计算出的最小时间。

以上图测试案例为例，模仿官方题解用二维矩阵的方式表示，可以很好地理解计算公式：

 

 AC代码

func leastInterval(tasks []byte, n int) int {
    tasksCnt:=len(tasks)
    m:=make(map[byte]int,tasksCnt)
    for _,task:=range tasks{
        m[task]++
    }
    maxExec,maxExecTasksCnt:=0,0//任务的最大执行次数和执行最大次数的任务数
    for _,v:=range m{
        if v>maxExec{
            maxExec,maxExecTasksCnt=v,1
        }else if v==maxExec{
            maxExecTasksCnt++
        }
    }
    if res:=(maxExec-1)*(n+1)+maxExecTasksCnt;res>tasksCnt{
        return res
    }
    return tasksCnt
}

感悟

一道考察数学的题目，当时只想到了最大执行任务次数，但是没想到对应的公式。