题目

给一些任务tasks需要尽快完成,但是有一个限制,相同任务必须间隔n个其他任务。

比如:

1
2
3
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

由于”A”是次数最多的任务,它会把任务序列分割成 A X X A X X A X X,因此每次迭代就是以次数最多的任务来分割,这样tasks完成时间最小。

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> task_count(26, 0);
for (char c : tasks) {
task_count[c - 'A']++;
}
sort(task_count.begin(), task_count.end()); // task_count.back()是次数最多的任务
int index = 0;
int count = 0;
while (task_count.back()) {
while(index <= n && task_count.back()) { // 每次迭代需要找到n个任务
if (index <= 25 && task_count[25-index]) { // 如果任务种类超过n,就不需要idle,需要减少对应的任务数
task_count[25-index]--;
}
count++;
index++;
}
index = 0;
sort(task_count.begin(), task_count.end()); // 已经找到n个任务,下一次需要重新排序
}
return count;
}
};

时间复杂度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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> task_count(26, 0);
for (char c : tasks) {
task_count[c - 'A']++;
}
int k = *max_element(task_count.begin(), task_count.end()); // 最多次数k
int p = 0;
for (auto count: task_count) {
if (count == k) p++;
}
size_t count = (n+1)*(k-1)+p;
return max(tasks.size(), count);
}
};

参考花花酱 LeetCode 621. Task Scheduler