1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// @Title: 任务调度器 (Task Scheduler)
// @Author: 15816537946@163.com
// @Date: 2020-06-25 07:15:36
// @Runtime: 4 ms
// @Memory: 6 MB
/*
 * @lc app=leetcode.cn id=621 lang=golang
 *
 * [621] 任务调度器
 *
 * https://leetcode-cn.com/problems/task-scheduler/description/
 *
 * algorithms
 * Medium (45.51%)
 * Likes:    118
 * Dislikes: 0
 * Total Accepted:    6.4K
 * Total Submissions: 14K
 * Testcase Example:  '["A","A","A","B","B","B"]\n2'
 *
 * 给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26
 * 种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单位时间内执行完。CPU
 * 在任何一个单位时间内都可以执行一个任务,或者在待命状态。
 *
 * 然而,两个相同种类的任务之间必须有长度为 n 的冷却时间,因此至少有连续 n 个单位时间内 CPU 在执行不同的任务,或者在待命状态。
 *
 * 你需要计算完成所有任务所需要的最短时间。
 *
 * 示例 1:
 *
 *
 * 输入: tasks = ["A","A","A","B","B","B"], n = 2
 * 输出: 8
 * 执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
 *
 *
 * 注:
 *
 *
 * 任务的总个数为 [1, 10000]。
 * n 的取值范围为 [0, 100]。
 *
 *
 */

// 动态规划
func leastInterval(tasks []byte, n int) int {
	if n == 0 {
		return len(tasks)
	}

	// 1. 存储任务数
	rec := [26]int{}
	for _, c := range tasks {
		rec[c-'A']++
	}

	// 2. 找到最多的任务数
	most := 0
	for _, num := range rec {
		if num > most {
			most = num
		}
	}

	// 3. 整个过程, 至少有idles个空挡需要被填
	idles := (most - 1) * (n + 1)

	// 使用每一个 task 去填充 idles
	for _, num := range rec {
		// 可以假想 idles+1 个空档,被 most 的 task 等间距n填充后,
		// 分割成了 most-1 个包含连续 n 个空档的区间
		// 然后,同样的任务,只能往每个区间中去填充。
		idles -= min(most-1, num)
		// 由于是使用 most 做的分割
		// 如果最后的 idles < 0 只能说明
		// len(tasks) > (most - 1) * (n + 1)+1
	}

	return len(tasks) + max(0, idles)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}