class Solution {
public:
long long taskSchedulerII(vector<int>& tasks, int space) {
}
};
2365. 任务调度器 II
给你一个下标从 0 开始的正整数数组 tasks ，表示需要 按顺序 完成的任务，其中 tasks[i] 表示第 i 件任务的 类型 。
同时给你一个正整数 space ，表示一个任务完成 后 ，另一个 相同 类型任务完成前需要间隔的 最少 天数。
在所有任务完成前的每一天，你都必须进行以下两种操作中的一种：
tasks 中的下一个任务请你返回完成所有任务所需的 最少 天数。
示例 1：
输入：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 天完成所有任务。
示例 2：
输入：tasks = [5,8,8,5], space = 2 输出：6 解释： 6 天完成所有任务的一种方法是： 第 1 天：完成任务 0 。 第 2 天：完成任务 1 。 第 3 天：休息。 第 4 天：休息。 第 5 天：完成任务 2 。 第 6 天：完成任务 3 。 可以证明无法少于 6 天完成所有任务。
提示：
1 <= tasks.length <= 1051 <= tasks[i] <= 1091 <= space <= tasks.length原站题解
cpp 解法, 执行用时: 240 ms, 内存消耗: 99.6 MB, 提交时间: 2023-06-06 09:33:17
class Solution {
public:
long long taskSchedulerII(vector<int>& tasks, int space) {
int n = tasks.size();
unordered_map<int, long long> mp;
for (int x : tasks) mp[x] = -1e18;
long long ans = 0;
for (int i = 0; i < n; i++) {
long long &last = mp[tasks[i]];
if (ans - last >= space) ans++, last = ans;
else ans = last + space + 1, last = ans;
}
return ans;
}
};
golang 解法, 执行用时: 132 ms, 内存消耗: 11.8 MB, 提交时间: 2023-06-06 09:32:51
func taskSchedulerII(tasks []int, space int) int64 {
ans := 0
last := map[int]int{}
for _, t := range tasks {
ans++ // 完成该任务，天数+1
if last[t] > 0 {
ans = max(ans, last[t]+space+1) // 看看是否要间隔 space 天
}
last[t] = ans // 记录上一次完成时间
}
return int64(ans)
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 168 ms, 内存消耗: 34.9 MB, 提交时间: 2023-06-06 09:32:31
class Solution:
def taskSchedulerII(self, tasks: List[int], space: int) -> int:
ans, last = 0, {}
for t in tasks:
ans += 1 # 完成该任务，天数+1
if t in last:
ans = max(ans, last[t] + space + 1) # 看看是否要间隔 space 天
last[t] = ans # 记录上一次完成时间
return ans