算法题：任务调度器

编码如写诗

发布于 2026-03-02 20:54:15

文章被收录于专栏：编码如写诗编码如写诗

算法题：任务调度器

聊回技术。

今天这道题,是我在刷LeetCode时看到的。题目叫"任务调度器",给定一个字符数组表示CPU需要执行的任务,每个任务用一个大写字母表示。

为啥选这道题?

因为看到大家讨论"加班"、"996",我突然想到——这不就是一个任务调度的问题吗?

如何合理安排任务,既能完成所有工作,又能让CPU"休息"的时间最少?

这不就是打工人梦寐以求的"高效工作"吗?

题目理解

给定一个字符数组tasks,表示CPU需要执行的任务。tasks[i]表示第i个任务的类型。

每个任务可以在1个单位时间内完成。

在任何一个单位时间内,CPU可以完成一个任务,或者处于待命状态。

但是,两个相同类型的任务之间必须有长度为n的冷却时间。

返回完成所有任务所需的最短时间。

示例:

输入: tasks = ["A","A","A","B","B","B"], n = 2
输出: 8
解释: 执行顺序为 A -> B -> (待命) -> A -> B -> (待命) -> A -> B

思路分析

暴力解法:尝试所有可能的排列组合,计算每个排列所需时间,取最小值。

这个思路的时间复杂度是O(k!),其中k是任务种类数,显然不可行。

贪心解法:

关键在于:出现次数最多的任务决定了总时间。

假设任务A出现了maxCount次,那么这些任务A之间至少要有n个单位时间的间隔。

也就是说,最后一个任务A之前,至少需要(maxCount - 1) * (n + 1)个单位时间。

再加上最后一个A本身,就是(maxCount - 1) * (n + 1) + 1个单位时间。

如果还有其他任务也出现了maxCount次,那么每个额外的这种任务都需要额外占用一个时间槽。

所以总时间至少是:(maxCount - 1) * (n + 1) + maxCountCount

其中maxCountCount是出现maxCount次的任务种类数。

但还有一种情况:如果任务太多,上述公式计算的时间可能小于实际任务数量(没有空闲时间)。

此时,最短时间就是所有任务的数量。

所以最终答案是:max(上述公式计算值, tasks.length)

复杂度分析

时间复杂度:O(n),只需要遍历一次任务数组统计任务数量
空间复杂度:O(1),最多有26个大写字母,空间固定

代码实现

package main

import (
"fmt"
)

func leastInterval(tasks []byte, n int) int {
// 统计每个任务出现的次数
 count := make([]int, 26)
for _, task := range tasks {
  count[task-'A']++
 }

// 找出最大出现次数
 maxCount := 0
for _, c := range count {
if c > maxCount {
   maxCount = c
  }
 }

// 统计出现maxCount次的任务数量
 maxCountCount := 0
for _, c := range count {
if c == maxCount {
   maxCountCount++
  }
 }

// 计算最短时间
// 情况1:有空闲时间
 timeWithIdle := (maxCount-1)*(n+1) + maxCountCount

// 情况2:没有空闲时间,就是任务总数
 timeWithoutIdle := len(tasks)

// 取较大值
if timeWithIdle > timeWithoutIdle {
return timeWithIdle
 }
return timeWithoutIdle
}

func main() {
// 测试用例1
 tasks1 := []byte{'A', 'A', 'A', 'B', 'B', 'B'}
 n1 := 2
 fmt.Printf("输入: tasks = %v, n = %d\n", tasks1, n1)
 fmt.Printf("输出: %d\n\n", leastInterval(tasks1, n1))
// 预期输出: 8

// 测试用例2
 tasks2 := []byte{'A', 'A', 'A', 'B', 'B', 'B'}
 n2 := 0
 fmt.Printf("输入: tasks = %v, n = %d\n", tasks2, n2)
 fmt.Printf("输出: %d\n\n", leastInterval(tasks2, n2))
// 预期输出: 6

// 测试用例3
 tasks3 := []byte{'A', 'A', 'A', 'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G'}
 n3 := 2
 fmt.Printf("输入: tasks = %v, n = %d\n", tasks3, n3)
 fmt.Printf("输出: %d\n", leastInterval(tasks3, n3))
// 预期输出: 10
}