{x}
blog image

Task Scheduler

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all 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.

After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.

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.

With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

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

Output: 10

Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

 

Constraints:

  • 1 <= tasks.length <= 104
  • tasks[i] is an uppercase English letter.
  • 0 <= n <= 100

Solution Explanation

This problem can be solved using a greedy approach. The core idea is to schedule the most frequent tasks as early as possible, while respecting the cooling-off period n. The solution leverages the fact that maximizing the time between occurrences of the most frequent tasks will minimize the overall schedule length.

Algorithm:

  1. Count Task Frequencies: Use a counter (e.g., a hash map or array) to count the occurrences of each task.

  2. Find Most Frequent Task: Determine the maximum frequency (x) among all tasks.

  3. Count Tasks with Maximum Frequency: Count the number of tasks (s) that have the maximum frequency x.

  4. Calculate Minimum Intervals: The minimum number of intervals needed is determined by the following formula: max(len(tasks), (x - 1) * (n + 1) + s).

    • len(tasks): The total number of tasks, representing the minimum possible time if there were no constraints.
    • (x - 1) * (n + 1): This represents the time needed to schedule the most frequent tasks, considering the cooling-off period. We subtract 1 from x because the last occurrence of the most frequent task doesn't require a cooling-off period after it. We add 1 to n to account for the task itself.
    • + s: We add s (the number of tasks with maximum frequency) to account for the fact that these tasks can be scheduled concurrently, reducing the overall time.

Time Complexity: O(N), where N is the number of tasks. Counting task frequencies and finding the maximum frequency takes linear time. The rest of the calculations are constant time.

Space Complexity: O(1). The space used by the frequency counter is constant because there are only 26 possible tasks (A-Z).

Code Explanation (Python):

from collections import Counter
 
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        cnt = Counter(tasks)  # Count task frequencies
        x = max(cnt.values()) # Find max frequency
        s = sum(v == x for v in cnt.values()) # Count tasks with max frequency
        return max(len(tasks), (x - 1) * (n + 1) + s) # Apply the formula

The Java, C++, Go, and C# code implementations follow the same logic with minor syntactic differences to suit their respective languages. They all efficiently achieve the greedy scheduling by focusing on the most frequent tasks and calculating the minimum intervals required.