loading

Task Scheduler — Step-by-Step Visualization

mediumLeetCode #621ArrayHash TableGreedySortingHeap (Priority Queue)

You are given an array of CPU `tasks`, each represented by a letter 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.

Algorithm Pattern

Greedy via Max-Heap

Key Idea

To minimize idle time, we should always prioritize the task with the highest remaining frequency. We use a Max-Heap to track frequencies. When a task is executed, it enters a 'cooldown queue' where it waits for `n` intervals before it can be added back to the heap.

Step-by-Step Approach

  1. Count the frequency of each task.
  2. Push all frequencies into a Max-Heap.
  3. While the heap or the cooldown queue is not empty:
  4. Increment the time/interval count.
  5. If the heap is not empty: pop the max frequency, decrement it, and (if > 0) add it to the cooldown queue with its available time (`time + n`).
  6. Check the queue: if any task's cooldown is over, push it back into the heap.

Common Gotchas

  • The total time is not just the number of tasks; it includes the 'idle' cycles where no task can be run due to constraints.

Related Problems

← All problems