Task Scheduler | Leetcode 621

Welcome to our deep dive on Task Scheduler (Leetcode 621). This greedy scheduling problem has an incredibly elegant pure mathematical solution.

Problem Statement

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.

Return the minimum number of intervals required to complete all tasks.

Example: tasks = ["A","A","A","B","B","B"], n = 2 => Output: 8 (Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.)

Approach: The Math Formula O(N)

Instead of actually simulating the CPU cycles with a Priority Queue, we can calculate the exact minimum time required using pure math.

The bottleneck is always the most frequent task(s). Let's say task A appears the most times, max_freq. We must schedule all As, separated by n empty slots for cooldown. A [n empty slots] A [n empty slots] A

This creates exactly (max_freq - 1) chunks of empty time between our A tasks! The length of each chunk is exactly n. So the base length of our sequence is: (max_freq - 1) * (n + 1).

What about the very last chunk? We need to add A itself to the very end! But what if there is a tie for the most frequent task? E.g. both A and B appear max_freq times. They will naturally cleanly bundle together at the end. We simply count how many tasks share this exact maximum frequency (num_max_tasks).

The mathematical formula is: minimum_time = (max_freq - 1) * (n + 1) + num_max_tasks

There is one edge case: What if n is so small (n=0 or 1), and there are so many different tasks that the calculated minimum time is physically shorter than the actual original tasks.length? That's impossible, because every task strictly takes at least 1 unit of time! So, our final answer must be max(tasks.length, calculated_time).

from collections import Counter

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freq = Counter(tasks)
        max_freq = max(freq.values())
        
        # Count identical frequency ties
        num_max_tasks = sum(1 for v in freq.values() if v == max_freq)
        
        # Pure mathematical optimally logical reliably exact calculation
        calculated_time = (max_freq - 1) * (n + 1) + num_max_tasks
        
        return max(len(tasks), calculated_time)

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (621)