任务调度器 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的情况,具体是如何计算需要休息的天数的?
▷🦆
算法在处理每个任务时都增加了天数,这是否意味着算法默认每天只能完成一个任务或休息?
▷