Question

2365. 任务调度器 II

English Version

题目描述

给你一个下标从 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 <= 105
• 1 <= tasks[i] <= 109
• 1 <= space <= tasks.length

解法

方法一：哈希表 + 模拟

我们可以用哈希表 $day$ 记录每个任务下一次可以被执行的时间，初始时 $day$ 中的所有值都为 $0$，用变量 $ans$ 记录当前时间。

遍历数组 $tasks$，对于每个任务 $task$，当前时间 $ans$ 加一，表示从上一次执行任务到现在已经过去了一天，如果此时 $day[task] \gt ans$，说明任务 $task$ 需要在第 $day[task]$ 天才能被执行，因此我们更新当前时间 $ans = \max(ans, day[task])$。然后更新 $day[task]$ 的值为 $ans + space + 1$，表示任务 $task$ 下一次可以被执行的时间为 $ans + space + 1$。

遍历结束后，将 $ans$ 返回即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $tasks$ 的长度。

class Solution:
  def taskSchedulerII(self, tasks: List[int], space: int) -> int:
    day = defaultdict(int)
    ans = 0
    for task in tasks:
      ans += 1
      ans = max(ans, day[task])
      day[task] = ans + space + 1
    return ans

class Solution {
  public long taskSchedulerII(int[] tasks, int space) {
    Map<Integer, Long> day = new HashMap<>();
    long ans = 0;
    for (int task : tasks) {
      ++ans;
      ans = Math.max(ans, day.getOrDefault(task, 0L));
      day.put(task, ans + space + 1);
    }
    return ans;
  }
}

class Solution {
public:
  long long taskSchedulerII(vector<int>& tasks, int space) {
    unordered_map<int, long long> day;
    long long ans = 0;
    for (int& task : tasks) {
      ++ans;
      ans = max(ans, day[task]);
      day[task] = ans + space + 1;
    }
    return ans;
  }
};

func taskSchedulerII(tasks []int, space int) (ans int64) {
  day := map[int]int64{}
  for _, task := range tasks {
    ans++
    if ans < day[task] {
      ans = day[task]
    }
    day[task] = ans + int64(space) + 1
  }
  return
}

function taskSchedulerII(tasks: number[], space: number): number {
  const day = new Map<number, number>();
  let ans = 0;
  for (const task of tasks) {
    ++ans;
    ans = Math.max(ans, day.get(task) ?? 0);
    day.set(task, ans + space + 1);
  }
  return ans;
}