leetcode
leetcode 2051 ~ 2100
任务调度器 II

任务调度器 II

难度:

标签:

题目描述

代码结果

运行时间: 120 ms, 内存: 34.4 MB


import java.util.*;
import java.util.stream.*;

/**
 * Solution for the given Leetcode problem using Java Streams.
 * The idea remains the same, but we utilize streams to handle the processing.
 */
public class SolutionStream {
    public int minDaysToCompleteTasks(int[] tasks, int space) {
        Map<Integer, Integer> lastPerformed = new HashMap<>();
        AtomicInteger days = new AtomicInteger();

        Arrays.stream(tasks).forEach(task -> {
            days.incrementAndGet();
            if (lastPerformed.containsKey(task)) {
                int lastDay = lastPerformed.get(task);
                if (days.get() - lastDay <= space) {
                    days.set(lastDay + space + 1);
                }
            }
            lastPerformed.put(task, days.get());
        });

        return days.get();
    }

    public static void main(String[] args) {
        SolutionStream sol = new SolutionStream();
        int[] tasks1 = {1, 2, 1, 2, 3, 1};
        int space1 = 3;
        System.out.println(sol.minDaysToCompleteTasks(tasks1, space1)); // Output: 9

        int[] tasks2 = {5, 8, 8, 5};
        int space2 = 2;
        System.out.println(sol.minDaysToCompleteTasks(tasks2, space2)); // Output: 6
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
哈希表中存储的是任务的最后完成日期,那么这个信息是如何确保任务按照顺序完成的?
哈希表存储每个任务的最后完成日期主要用于判断任务是否能够按照规定的间隔(space)再次执行。通过追踪每个任务的完成时间,算法在遍历任务数组时能够按照任务数组的顺序检查每个任务是否满足间隔条件。因此,任务的顺序由输入的任务数组的顺序决定,算法确保在此顺序下,每个任务都在满足间隔要求的最早可能时间执行。
🦆
解释中提到的‘如果大于space,则可以直接执行此任务’的逻辑是否意味着即使有足够的间隔也可能因为任务顺序而导致不能立即执行?
当哈希表中记录的最后完成日期与当前日期的差值大于space时,任务可以立即执行。这意味着任务的执行仅依赖于它自身的间隔满足情况,而与其他任务无关。如果当前任务的间隔已足够,它将立即执行,无论其他任务的状态如何。因此,即使有足够的间隔,任务也总是按照输入数组的顺序执行,不会因为其他任务的安排而延迟。
🦆
对于连续出现的相同任务,算法如何处理间隔小于space的情况,具体是如何计算需要休息的天数的?
对于连续出现的相同任务,如果当前天数与上次完成该任务的日期的差值小于或等于space,则说明任务不能立即执行。此时,算法会将当前天数设置为上一次任务完成后需等待的最小天数,即上次完成日期加上间隔space再加一天。这样确保了每个任务都在满足间隔要求后的第一个可能日子执行。
🦆
算法在处理每个任务时都增加了天数,这是否意味着算法默认每天只能完成一个任务或休息?
算法中的天数增加逻辑(每执行一个任务,天数加一)确实表明在模拟过程中,默认每天只处理一个任务或者休息。这是为了简化任务执行间隔的计算和调度。在实际情况中,可能一天能完成多个任务,但在这个算法模型中,为了保持间隔和执行顺序的清晰,采用了每天最多执行一个任务的简化模型。

相关问题