LeetMotion
You are given an array of CPU tasks tasks, where tasks[i] is an uppercase english character from A to Z. You are also given an integer n.
Each CPU cycle allows the completion of a single task, and tasks may be completed in any order.
The only constraint is that identical tasks must be separated by at least n CPU cycles, to cooldown the CPU.
Return the minimum number of CPU cycles required to complete all tasks.
1 <= tasks.length <= 10000 <= n <= 100Why do it this way? This is the most direct translation of the problem statement. We simulate the CPU tick by tick. For every tick, we look at all available tasks, check if they are on cooldown by scanning the last `N` executed tasks, and pick the most frequent one. It works, but it's slow because checking the cooldown history on every tick takes extra time.
You have a group of workers who can only do one task per hour, and need N hours of break before repeating it. Every single hour, you look at your logbook of the past N hours to see who is allowed to work, then pick the person who has the most work left.
function leastInterval(tasks, n):
counts = map of task frequencies
time = 0
history = [] // to track cooldowns
while tasks remain:
find available task with highest frequency
if task found:
execute task (decrement count)
add to history
else:
add idle to history
time += 1
return timeWhy do it this way? We still simulate time, but we optimize how we pick the next task. Instead of scanning arrays, we put all available tasks in a Max-Heap based on frequency so picking the best task is instant. When we execute a task, we put it in a Cooldown Queue along with its "unlock time". If the heap is empty, we don't have to simulate every idle tick—we can just "fast-forward" time to whenever the first task in the queue unlocks!
Instead of checking every minute if a worker is off break, you give them a buzzer that goes off exactly when their break is done. If no one is available to work, you just fast-forward your clock to whenever the earliest buzzer is set to ring.
function leastInterval(tasks, n):
maxHeap = build_max_heap(task_frequencies)
queue = [] // stores [remaining_count, unlock_time]
time = 0
while maxHeap or queue:
time += 1
if not maxHeap:
time = queue[0].unlock_time // fast-forward
else:
count = maxHeap.pop_max() - 1
if count > 0:
queue.push([count, time + n])
if queue and queue[0].unlock_time == time:
maxHeap.push(queue.pop().count)
return timeWhy do it this way? Instead of simulating time, let's look at the structure. The most frequent task creates "gaps". If task A appears 5 times, it creates 4 gaps of size N. We initially assume all these gaps are idle slots. Then, we just iterate through the rest of the tasks and "slot them in" to the gaps, subtracting from our total idle count. The final answer is just `len(tasks) + idle_slots`!
You have a bookshelf with pre-built empty dividers for your largest set of books. You just count how many empty slots you have, then take your remaining books and slot them into the gaps. If you run out of empty gaps, you just make the bookshelf wider.
function leastInterval(tasks, n):
counts = array of 26 frequencies
counts.sort()
max_freq = counts[25]
idle_slots = (max_freq - 1) * n
for i from 24 down to 0:
idle_slots -= min(max_freq - 1, counts[i])
return max(0, idle_slots) + len(tasks)Why do it this way? We can reduce the logic into a pure O(1) formula (after counting frequencies). The absolute minimum time required is dictated by the most frequent task. It needs (maxf - 1) gaps, and each gap is length (n + 1). If multiple tasks tie for the max frequency, they append to the end. The final formula is exactly (maxf - 1) * (n + 1) + maxCount. If the array is larger than this, it just means we didn't need any idle time, so we return len(tasks).
Imagine building a house. The foundation takes 3 weeks, and you can't build the walls until it's done. You don't need to simulate every single day of the workers' lives. You just look at the absolute longest bottleneck, calculate the exact minimum weeks it will take to cross that bottleneck, and that's your answer.
function leastInterval(tasks, n):
max_freq = max(task_frequencies)
num_max_tasks = count_tasks_with_freq(max_freq)
bottleneck_time = (max_freq - 1) * (n + 1) + num_max_tasks
return max(len(tasks), bottleneck_time)
Discussion
…