题目描述

给你一个下标从 0 开始的正整数数组 tasks，表示需要 按顺序 完成的任务，其中 tasks[i] 表示第 i 件任务的 类型。

同时给你一个正整数 space，表示一个任务完成 后，另一个 相同 类型任务完成前需要间隔的 最少 天数。

在所有任务完成前的每一天，你都必须进行以下两种操作中的一种：

• 完成 tasks 中的下一个任务
• 休息一天

请你返回完成所有任务所需的 最少 天数。

样例

输入：tasks = [1,2,1,2,3,1], space = 3
输出：9
解释：
9 天完成所有任务的一种方法是：
第 1 天：完成任务 0。
第 2 天：完成任务 1。
第 3 天：休息。
第 4 天：休息。
第 5 天：完成任务 2。
第 6 天：完成任务 3。
第 7 天：休息。
第 8 天：完成任务 4。
第 9 天：完成任务 5。
可以证明无法少于 9 天完成所有任务。

输入：tasks = [5,8,8,5], space = 2
输出：6
解释：
6 天完成所有任务的一种方法是：
第 1 天：完成任务 0。
第 2 天：完成任务 1。
第 3 天：休息。
第 4 天：休息。
第 5 天：完成任务 2。
第 6 天：完成任务 3。
可以证明无法少于 6 天完成所有任务。

限制

• 1 <= tasks.length <= 10^5
• 1 <= tasks[i] <= 10^9
• 1 <= space <= tasks.length

算法

(哈希表) $O(n)$

1. 按顺序遍历任务数组，使用变量 $day$ 记录天数，即完成当前任务后的下一天。天数从 $0$ 开始。
2. 使用哈希表记录上一次完成同种任务的 $day$。
3. 遍历时，如果发现上一次完成同种任务时的间隔天数不足 $space$，则重置 $day := last(t) + space + 1$。
4. 完成当前任务后 $day := day + 1$。

时间复杂度

• 遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

#define LL long long

class Solution {
public:
    LL taskSchedulerII(vector<int>& tasks, int space) {
        unordered_map<int, LL> last;
        LL day = 0;

        for (int t : tasks) {
            if (last.find(t) != last.end() && day - last[t] <= space)
                day = last[t] + space + 1;

            last[t] = day;
            day++;
        }

        return day;
    }
};