Back to Problems

Task Scheduler

Medium
greedy

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling interval 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.

Greedy Insight: The task with maximum frequency determines the minimum time. Arrange the most frequent task first with gaps of n, then fill the gaps with other tasks.

Why Greedy Works: The bottleneck is the most frequent task. We need (maxFreq - 1) * (n + 1) + countOfMaxFreqTasks intervals at minimum. However, if we have many diverse tasks, they might fill all the gaps, so the answer is max(formula_result, total_tasks).

Example 1

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B. There are a total of 8 intervals.

Example 2

Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B. There is no need for idle intervals as all tasks can be scheduled without violating the cooling constraint.

Example 3

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: With n = 0, there is no cooling constraint. We can execute all 6 tasks back-to-back in 6 intervals.

Constraints

  • •1 <= tasks.length <= 10^4
  • •tasks[i] is an uppercase English letter
  • •0 <= n <= 100
Show Hints (4)
Hint 1: Count the frequency of each task.
Hint 2: The most frequent task creates the most idle time.
Hint 3: Calculate idle slots based on (maxFreq - 1) * n, then fill with other tasks.
Hint 4: The answer is max(tasks.length, calculated_intervals).
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?