任务调度器 II

标签: 数组 哈希表 模拟

难度: Medium

给你一个下标从 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

Submission

运行时间: 120 ms

内存: 34.4 MB

class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        days=0
        dealtask={}#记录每类任务最后一次完成时间（第几天完成，从0开始）
        for t in tasks:
            days+=1
            if t not in dealtask:
                dealtask[t]=days
            else:
                if days-dealtask[t]>space:
                    dealtask[t]=days
                else:
                    days=dealtask[t]+space+1
                    dealtask[t]=days
        return days

Explain

此题解采用了哈希表来记录每种任务最后一次完成的日期。对于每一个任务，我们首先递增天数（模拟每天完成任务），然后检查该任务是否之前完成过。如果完成过，我们比较当前日期与该任务上次完成日期的差值是否大于space。如果大于space，说明可以直接执行此任务，更新该任务的最新完成日期。如果不大于，则必须等待直到满足space的要求，然后更新完成日期。这种方式确保了在满足间隔要求的情况下，尽可能早地完成所有任务。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        days = 0  # 初始化天数
        dealtask = {}  # 哈希表记录每种任务的最后完成日期
        for t in tasks:
            days += 1  # 每处理一个任务，天数加一
            if t in dealtask and days - dealtask[t] <= space:
                # 如果任务已经完成过，并且未满足间隔要求，需要调整天数
                days = dealtask[t] + space + 1
            # 更新这个任务的最新完成日期
            dealtask[t] = days
        return days

Explore

哈希表存储每个任务的最后完成日期主要用于判断任务是否能够按照规定的间隔（space）再次执行。通过追踪每个任务的完成时间，算法在遍历任务数组时能够按照任务数组的顺序检查每个任务是否满足间隔条件。因此，任务的顺序由输入的任务数组的顺序决定，算法确保在此顺序下，每个任务都在满足间隔要求的最早可能时间执行。

当哈希表中记录的最后完成日期与当前日期的差值大于space时，任务可以立即执行。这意味着任务的执行仅依赖于它自身的间隔满足情况，而与其他任务无关。如果当前任务的间隔已足够，它将立即执行，无论其他任务的状态如何。因此，即使有足够的间隔，任务也总是按照输入数组的顺序执行，不会因为其他任务的安排而延迟。

对于连续出现的相同任务，如果当前天数与上次完成该任务的日期的差值小于或等于space，则说明任务不能立即执行。此时，算法会将当前天数设置为上一次任务完成后需等待的最小天数，即上次完成日期加上间隔space再加一天。这样确保了每个任务都在满足间隔要求后的第一个可能日子执行。

算法中的天数增加逻辑（每执行一个任务，天数加一）确实表明在模拟过程中，默认每天只处理一个任务或者休息。这是为了简化任务执行间隔的计算和调度。在实际情况中，可能一天能完成多个任务，但在这个算法模型中，为了保持间隔和执行顺序的清晰，采用了每天最多执行一个任务的简化模型。