【哈希表, 数组】任务调度器 II

题目

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 <= 10^5
• 1 <= tasks[i] <= 10^9
• 1 <= space <= tasks.length

解题

方法一：哈希表

思路

维护一个哈希表，映射关系是：任务类型->上一次执行的时间，维护执行某个任务之前已经经过的天数(day)初始化为 0。

因为要按顺序完成任务，所以可以直接正序遍历任务数组：

• 首先取出该类型的任务(task)上一次的执行时间(last_time)，如果第一次做这个任务取不到的话就把执行时间设置为一个很小的值(-INF)保证第一次可以直接执行。
• 如果 day > last_time + space 说明间隔时间已经过了，可以直接执行任务 ++day。
• 否则说明间隔时间还没过，要等间隔时间过后才能执行任务 day = last_time + space + 1.
• 最后维护哈希表(last_time = day)。

返回天数(day)即可。

代码

class Solution {
public:
    long long taskSchedulerII(vector<int>& tasks, int space) {
        unordered_map<int, long long> mp;
        long long day = 0;
        for (const int& task : tasks) {
            if (mp.find(task) == mp.end()) mp[task] = numeric_limits<long long>::min();
            long long& last_time = mp[task];
            if (day > last_time + space) ++day;
            else day = last_time + space + 1;
            last_time = day;
        }
        return day;
    }
};

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