Leetcode Link: 6174. 任务调度器 II - 力扣(LeetCode)

题目

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

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

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

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

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

84场双周赛T3,做不出来。卡了一个小时,完全是思路打不开,刷题量不够,并且思路收到了任务调度器的影响。

解法一

思路: 本题特殊在任务的顺序已经确定了,不可更改,因此直接进行模拟就行。

模拟天数的变化。利用字典保存每个任务上次执行的时间,并且在每次执行任务时更新这个时间。有如下两种情况

  1. 当当前任务距离上次执行的间隔不够 spacetoday 需要更新到对应的天数才行
  2. 当当前任务可以执行的时候,执行即可,并在字典中保存本次执行的天数。

题解

class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        today = 0  # 今天(是第几天,因此初始化为0)
        d_last_task = {}
        for task in tasks:
            today += 1  # 每次都进天数都加1,即过了一天
            if task in d_last_task.keys() and d_last_task[task]+space+1 > today: # 距离上次间隔不够
                today = d_last_task[task] + space + 1
                d_last_task[task] = today
            else: # 没遇到过这个任务或者距离间隔够了
                d_last_task[task] = today
                
        return today

启发和联系

同类型问题任务调度器