任务调度器
难度:
标签:
题目描述
代码结果
运行时间: 45 ms, 内存: 17.7 MB
/*
* 题目思路:
* 利用 Java Stream API 简化代码逻辑。我们依然需要统计每种任务的频率,
* 然后计算最短时间。与传统 Java 方法相比,Stream 提供了更简洁的代码风格。
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public int leastInterval(char[] tasks, int n) {
Map<Character, Long> freqMap = Arrays.stream(tasks)
.boxed()
.collect(Collectors.groupingBy(c -> c, Collectors.counting()));
List<Long> frequencies = new ArrayList<>(freqMap.values());
Collections.sort(frequencies, Collections.reverseOrder());
long maxCount = frequencies.get(0);
long idleSlots = (maxCount - 1) * n;
for (long freq : frequencies) {
idleSlots -= Math.min(maxCount - 1, freq);
}
return (int) (idleSlots > 0 ? idleSlots + tasks.length : tasks.length);
}
}
解释
方法:
该题解的思路是统计任务的频率,找到频率最高的任务。根据最高频率和冷却时间,计算完成所有任务所需的最短时间间隔。具体来说:
1. 如果冷却时间 n 为0,直接返回任务的总数,因为任务可以连续执行。
2. 统计每个任务的频率,找到最高频率 max_freq。
3. 计算最高频率的任务数量 max_count。
4. 计算最短时间间隔,取以下两者的较大值:
- 任务总数 len(tasks)。
- (max_freq - 1) * (n + 1) + max_count,其中 (max_freq - 1) * (n + 1) 表示在最高频率的任务之间插入冷却时间后所需的时间单位,max_count 表示最高频率的任务本身所需的时间单位。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
如何计算最高频率任务的数量max_count,能否详细说明其在算法中的实际应用和意义?
▷🦆
如果任务的种类数量非常多,但每种任务的出现频率都很低,这种情况下算法的效率如何?会不会存在计算上的不必要复杂性?
▷🦆
算法中提到使用Counter来统计任务频率,这种数据结构在处理大规模数据时的性能如何?
▷