Task Scheduler

GreedyHeap

30 min

Problem Statement

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle. However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks. Return the least number of units of times that the CPU will take to finish all the given tasks.

Example

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2

tasks: [A, A, A, A, A, A, B, C, D, E, F, G], n: 2

Output: 16

Output: 8

The optimal schedule is: A -> B -> idle -> A -> B -> idle -> A -> B.

Approach 1: Max Heap with Queue

The first approach uses a simulation-based greedy strategy with a max heap to track task frequencies and a queue to handle cooldown periods.

Approach 1: Max Heap

Time: O(n log 26) = O(n)Space: O(26) = O(1)

The key insight is to process the most frequent tasks first using a max heap. This greedy approach ensures we always execute the task with the highest frequency when possible, minimizing idle time. We simulate the execution process by processing up to `n+1` tasks in each cycle, where `n` is the cooldown period.

Algorithm Steps

Count the frequency of each task.
Use a max heap to store the frequencies.
While the heap is not empty:
Create a temporary list to store tasks for the current cycle.
Execute up to `n+1` tasks, taking the most frequent ones from the heap.
Add the executed tasks back to the temporary list with decremented frequencies if they are not finished.
Add the tasks from the temporary list back to the heap.
Add the cycle length to the total time. If the heap is empty, add the number of tasks in the cycle. Otherwise, add `n+1`.

Task Scheduler

Greedy with Max Heap

Input: tasks = [A, A, A, A, A, A, B, C, D, E, F, G], n = 2

Output: 0

Progress1 / 1

Ready to start the visualization

Max Heap

Cooldown Queue

Time

Task Scheduler Solution


from collections import Counter, deque
import heapq

class Solution:
    def leastInterval(self, tasks: list[str], n: int) -> int:
        count = Counter(tasks)
        max_heap = [-cnt for cnt in count.values()]
        heapq.heapify(max_heap)
        
        time = 0
        q = deque() # [-cnt, idle_time]
        
        while max_heap or q:
            time += 1
            
            if max_heap:
                cnt = 1 + heapq.heappop(max_heap)
                if cnt:
                    q.append([cnt, time + n])
            
            if q and q[0][1] == time:
                heapq.heappush(max_heap, q.popleft()[0])
        return time

Approach 2: Greedy Mathematical Formula

The second approach uses a mathematical greedy strategy to calculate the minimum time directly without simulation, making it more efficient.

Approach 2: Greedy Mathematical

Time: O(n)Space: O(1)

This greedy approach uses mathematical calculation to determine the minimum time directly. The key insight is that the task with the highest frequency determines the minimum number of intervals needed. We calculate idle slots and fill them optimally with other tasks.

Algorithm Steps

Count the frequency of each task type (26 letters max).
Sort the frequency array to find the most frequent task.
Calculate the number of intervals: `max_freq - 1`.
Calculate initial idle slots: `(max_freq - 1) × n`.
For each task type, subtract its count from idle slots:
If frequency equals max frequency, subtract `max_freq - 1`.
Otherwise, subtract the full frequency count.
Return `max(tasks.length, tasks.length + remaining_idle_slots)`.

Task Scheduler

Greedy Mathematical Approach

Input: tasks = [A, A, A, A, A, A, B, C, D, E, F, G], n = 2

Output: ...

Progress1 / 1

Ready to start the visualization

Task Counts (sorted)

No data to display

Max Intervals

Idle Slots

Result

...

Task Scheduler Greedy Solution


def leastInterval(tasks, n):
    count = [0] * 26
    
    # Count frequency of each task
    for task in tasks:
        count[ord(task) - ord('A')] += 1
    
    # Sort counts in ascending order
    count.sort()
    
    # Calculate maximum intervals needed
    max_count = count[25] - 1
    idle_slots = max_count * n
    
    # Fill idle slots with other tasks
    for i in range(25):
        if count[i] == count[25]:
            idle_slots -= max_count
        else:
            idle_slots -= count[i]
    
    # Return total time needed
    return max(len(tasks), len(tasks) + idle_slots)