# 19.03.2024 [621. Task Scheduler]
Count CPU cycles if task can't run twice in `n` cycles #medium
19.03.2024
621. Task Scheduler medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/543
Problem TLDR
Count CPU cycles if task can’t run twice in n
cycles #medium
Intuition
Let’s try to understand the problem first, by observing the example:
// 0 1 2 3 4 5 6 7
// a a a b b b c d n = 3
// a . . . a . . . a
// b . . . b . . . b
// c d i i
One inefficient way is to take tasks by their frequency, store availability and adjust cycle forward if no task is available. This solution will take O(n) time but with big constant of iterating and sorting the frequencies [26]
array.
The clever way is to notice the pattern of how tasks are: there are empty slots between the most frequent task(s).
Approach
In the interview I would choose the first way.
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun leastInterval(tasks: CharArray, n: Int): Int {
val f = IntArray(128); for (c in tasks) f[c.code]++
val maxFreq = f.max()
val countOfMaxFreq = f.count { it == maxFreq }
val slotSize = n - (countOfMaxFreq - 1)
val slotsCount = (maxFreq - 1) * slotSize
val otherTasks = tasks.size - maxFreq * countOfMaxFreq
val idles = max(0, slotsCount - otherTasks)
return tasks.size + idles
}
pub fn least_interval(tasks: Vec<char>, n: i32) -> i32 {
let mut f = vec![0; 128]; for &c in &tasks { f[c as usize] += 1 }
let maxFreq = f.iter().max().unwrap();
let countOfMaxFreq = f.iter().filter(|&x| x == maxFreq).count() as i32;
let slotsCount = (maxFreq - 1) * (n - countOfMaxFreq + 1);
let otherTasks = tasks.len() as i32 - maxFreq * countOfMaxFreq;
tasks.len() as i32 + (slotsCount - otherTasks).max(0)
}