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

解题思路

解题思路

这道题的核心思想是贪心算法。我们需要尽可能早地完成每个任务，但同时要满足相同类型任务之间的间隔限制。

基本思路：

  1. 维护一个哈希表记录每种任务类型上次完成的天数
  2. 遍历所有任务，对于每个任务：
    • 如果是首次遇到该类型任务，直接执行
    • 如果之前执行过该类型任务，检查距离上次执行是否满足 space 天的间隔
    • 如果不满足间隔要求，需要等待到满足条件的那一天

关键点：

  • 当前天数从1开始计算
  • 对于重复任务类型，需要确保与上次执行间隔至少 space 天
  • 贪心策略：尽早完成每个任务，只在必要时休息

算法步骤：

  1. 使用哈希表 lastDay 记录每种任务类型最后完成的天数
  2. 初始化当前天数 currentDay = 1
  3. 遍历所有任务：
    • 如果该任务类型之前执行过，计算需要等待到的最早天数
    • 更新当前天数和任务完成记录
  4. 返回最终天数

时间复杂度为 O(n)，空间复杂度为 O(k)，其中 k 为不同任务类型的数量。

代码实现

class Solution {
public:
    long long taskSchedulerII(vector<int>& tasks, int space) {
        unordered_map<int, long long> lastDay;
        long long currentDay = 1;
        
        for (int task : tasks) {
            if (lastDay.count(task)) {
                // 如果之前执行过这种任务，需要检查间隔
                long long earliestDay = lastDay[task] + space + 1;
                currentDay = max(currentDay, earliestDay);
            }
            // 更新该任务类型的最后执行天数
            lastDay[task] = currentDay;
            currentDay++;
        }
        
        return currentDay - 1;
    }
};

class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        last_day = {}
        current_day = 1
        
        for task in tasks:
            if task in last_day:
                # 如果之前执行过这种任务，需要检查间隔
                earliest_day = last_day[task] + space + 1
                current_day = max(current_day, earliest_day)
            
            # 更新该任务类型的最后执行天数
            last_day[task] = current_day
            current_day += 1
        
        return current_day - 1

public class Solution {
    public long TaskSchedulerII(int[] tasks, int space) {
        Dictionary<int, long> lastDay = new Dictionary<int, long>();
        long currentDay = 1;
        
        foreach (int task in tasks) {
            if (lastDay.ContainsKey(task)) {
                // 如果之前执行过这种任务，需要检查间隔
                long earliestDay = lastDay[task] + space + 1;
                currentDay = Math.Max(currentDay, earliestDay);
            }
            // 更新该任务类型的最后执行天数
            lastDay[task] = currentDay;
            currentDay++;
        }
        
        return currentDay - 1;
    }
}

var taskSchedulerII = function(tasks, space) {
    const lastDay = new Map();
    let currentDay = 1;
    
    for (const task of tasks) {
        if (lastDay.has(task)) {
            // 如果之前执行过这种任务，需要检查间隔
            const earliestDay = lastDay.get(task) + space + 1;
            currentDay = Math.max(currentDay, earliestDay);
        }
        // 更新该任务类型的最后执行天数
        lastDay.set(task, currentDay);
        currentDay++;
    }
    
    return currentDay - 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n)
空间复杂度O(k)

其中 n 是任务数量，k 是不同任务类型的数量。

相关题目