Task Scheduler - Video Solutions

Problem Overview: You are given a list of CPU tasks represented by characters and a cooldown interval n. The same task must be separated by at least n intervals. The goal is to compute the minimum number of time units required to finish all tasks, including idle slots if necessary.

Approach 1: Max Frequency Task-Based Greedy (O(n) time, O(1) space)

This approach relies on counting how often each task appears. The task with the highest frequency determines the schedule structure because its occurrences must be spaced by at least n intervals. Suppose the most frequent task appears maxFreq times. These tasks create maxFreq - 1 gaps that must each hold n other tasks or idle slots. The minimal frame size becomes (maxFreq - 1) * (n + 1). If multiple tasks share the same maximum frequency, their last occurrences extend the final frame. The final answer is max(totalTasks, (maxFreq - 1) * (n + 1) + countMax).

This works because the optimal schedule always spreads the most frequent tasks first and fills remaining gaps with other tasks. Counting frequencies with an array of size 26 keeps the space constant. The method heavily relies on greedy reasoning and efficient counting. In interviews, this formula-based reasoning shows strong pattern recognition and leads directly to the optimal solution.

Approach 2: Priority Queue (Heap) Simulation (O(n log k) time, O(k) space)

This approach simulates the scheduling process using a max heap. First, count task frequencies using a map or array. Push the frequencies into a max heap so the most frequent task is always processed first. At each cycle of length n + 1, repeatedly pop the most frequent tasks and execute them. After execution, decrease their remaining count and temporarily store them until the cycle ends.

When the cycle finishes, push any remaining tasks back into the heap. If the heap becomes empty early, idle intervals fill the remaining part of the cycle. Continue until all tasks are completed. This approach models the CPU scheduling process explicitly and uses a heap (priority queue) along with basic array counting.

The heap simulation is easier to reason about when deriving the greedy rule from scratch. It also generalizes well to variations where cooldown rules or task weights change.

Recommended for interviews: The greedy max-frequency formula is what most interviewers expect for this problem because it runs in O(n) time with constant space and demonstrates strong insight into scheduling constraints. The heap simulation is still valuable because it shows how to model the scheduling process step by step. Starting with the heap approach and then optimizing to the greedy formula is a strong interview progression.