# Task Scheduler
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/task-scheduler)
Canonical: https://scaleengineer.com/dsa/problems/task-scheduler
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Token Bucket](https://scaleengineer.com/algorithms/token-bucket)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [IBM](https://scaleengineer.com/companies/ibm), [Intuit](https://scaleengineer.com/companies/intuit), [Roblox](https://scaleengineer.com/companies/roblox), [Snowflake](https://scaleengineer.com/companies/snowflake), [Salesforce](https://scaleengineer.com/companies/salesforce), [Zeta](https://scaleengineer.com/companies/zeta), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Rubrik](https://scaleengineer.com/companies/rubrik), [Remitly](https://scaleengineer.com/companies/remitly), [zeta suite](https://scaleengineer.com/companies/zeta-suite)
---
## Problem
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`

# Approaches
## Simulation with Sorting
This approach simulates the scheduling process time unit by time unit. At each step, it decides which task to run based on which tasks are available (not in cooldown) and have the highest frequency. To find the highest frequency task, it sorts the frequency counts at each time step.
**Time:** O(max_freq * (n + U log U)), where `max_freq` is the maximum frequency of any task, `n` is the cooldown, and `U` is the number of unique tasks (26). The outer loop runs `max_freq` times, and inside we sort (U log U) and loop `n` times. Since U is constant, this simplifies to O(max_freq * n). · **Space:** O(1), as the frequency array size is fixed at 26.
**Pros:** Relatively straightforward to conceptualize as a direct simulation.; Correctly models the greedy choice of picking the most frequent task.
**Cons:** Inefficient due to repeated sorting of the frequency array.; The time complexity is dependent on the maximum frequency and the cooldown period `n`, which can be suboptimal.
### Explanation
First, we count the frequencies of all tasks and store them in an array of size 26. The core of this method is a loop that continues as long as there are tasks left to be scheduled. In each iteration of this main loop, we simulate one 'cycle' of scheduling. A cycle consists of `n+1` time slots. We sort the frequency array in ascending order so that `counts[25]` holds the count of the most frequent task. We then iterate `n+1` times. In each of these sub-iterations, we try to schedule a task. We pick from the most frequent available tasks. After scheduling a task, we decrement its count. We increment our total `time` counter for each slot in the cycle, whether it's filled by a task or an idle moment. After the cycle of `n+1` slots is complete, we re-sort the frequency array because the frequencies have changed. The simulation ends when the count of the most frequent task becomes zero, meaning all tasks have been scheduled. The final `time` is our answer.

```java
import java.util.Arrays;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] counts = new int[26];
        for (char task : tasks) {
            counts[task - 'A']++;
        }
        Arrays.sort(counts);
        int time = 0;
        while (counts[25] > 0) {
            int i = 0;
            // A cycle of n+1 intervals
            while (i <= n) {
                // If the most frequent task is done, we can stop this cycle
                if (counts[25] == 0) {
                    break;
                }
                // Schedule a task if available
                if (i < 26 && counts[25 - i] > 0) {
                    counts[25 - i]--;
                }
                time++;
                i++;
            }
            Arrays.sort(counts);
        }
        return time;
    }
}
```
### Algorithm
- Create a frequency map `counts` of size 26 for tasks 'A' through 'Z'.
- Populate `counts` by iterating through the input `tasks` array.
- Sort the `counts` array to easily find the most frequent tasks.
- Initialize `time = 0`.
- Loop as long as the most frequent task count (`counts[25]`) is greater than 0:
  - In each outer loop, simulate one cycle of execution.
  - Iterate up to `n + 1` times to represent one full cooldown cycle.
  - In each step of the cycle, if there's a task available (from most frequent to least frequent), decrement its count.
  - Increment `time` for each task or idle slot in the cycle.
  - After each full cycle, re-sort the `counts` array to update the order of task frequencies.
- Return the total `time`.

## Simulation with Priority Queue
This approach also simulates the scheduling process but uses more appropriate data structures for efficiency. A max-priority queue is used to always have quick access to the task with the highest remaining frequency. This avoids the need for repeated sorting.
**Time:** O(L log U), where `L` is the number of tasks and `U` is the number of unique tasks (26). Since `U` is a constant, the complexity is effectively O(L). This is because each task is added and removed from the priority queue once. · **Space:** O(1), as the frequency map and priority queue will hold at most 26 unique tasks.
**Pros:** More efficient than the sorting-based simulation.; Represents a standard and robust greedy algorithm for scheduling problems.; Efficiently finds the highest frequency task using a priority queue.
**Cons:** More complex to implement compared to the mathematical approach.; It is still a simulation and not as performant as a direct calculation.
### Explanation
This greedy approach aims to schedule the most frequent tasks as early as possible to minimize idle time. First, we count task frequencies. Then, we use a max-priority queue to store these frequencies, allowing us to efficiently retrieve the task with the highest count.

The simulation proceeds in rounds. Each round represents a time interval of `n + 1` slots. In each round, we try to execute `n + 1` tasks. We poll up to `n + 1` tasks from the priority queue (the ones with the highest frequencies). We decrement their frequencies and store them temporarily. After the round, we add the tasks whose frequencies are still positive back into the priority queue.

The time elapsed in each round is `n + 1`, unless it's the final round where no more tasks are left, in which case the time elapsed is just the number of tasks executed in that final round. The total time is the sum of time from all rounds.

```java
import java.util.PriorityQueue;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char t : tasks) {
            counts.put(t, counts.getOrDefault(t, 0) + 1);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.addAll(counts.values());

        int time = 0;
        while (!pq.isEmpty()) {
            List<Integer> tempList = new ArrayList<>();
            int cycle = n + 1;
            
            // Execute tasks in one cycle
            for (int i = 0; i < cycle; i++) {
                if (!pq.isEmpty()) {
                    tempList.add(pq.poll());
                }
            }

            // Decrement frequency and add back to pq if not finished
            for (int freq : tempList) {
                if (freq - 1 > 0) {
                    pq.add(freq - 1);
                }
            }

            // Calculate time
            time += pq.isEmpty() ? tempList.size() : cycle;
        }
        return time;
    }
}
```
### Algorithm
- Count the frequency of each task.
- Create a max-priority queue and add all non-zero frequencies to it.
- Initialize `time = 0`.
- Loop while the priority queue is not empty:
  - Create a temporary list to hold tasks for the current execution cycle.
  - A cycle has a length of `n + 1`.
  - For up to `n + 1` times, poll a task from the priority queue if it's not empty and add it to the temporary list.
  - After filling the cycle, iterate through the tasks in the temporary list. Decrement their frequencies and add them back to the priority queue if their count is still greater than zero.
  - Add to the total `time`. If the priority queue is now empty, it was the last cycle, so add the number of tasks executed (`tempList.size()`). Otherwise, a full cycle of `n + 1` slots passed (filled with tasks or idles).
- Return the total `time`.

## Mathematical Calculation
This approach avoids simulation entirely and calculates the minimum time using a mathematical formula. The insight is that the schedule length is determined by the most frequent task, which acts as a bottleneck.
**Time:** O(L), where `L` is the number of tasks. The initial frequency counting takes O(L) time. The subsequent passes over the 26-element frequency array take constant time. · **Space:** O(1), as the frequency array size is fixed at 26.
**Pros:** Extremely efficient with linear time complexity.; Simple and concise implementation once the formula is understood.; Avoids complex data structures and simulations.
**Cons:** The logic behind the formula might not be immediately obvious without careful reasoning and derivation.
### Explanation
The most efficient way to solve this problem is to identify the primary constraint on the schedule's length. This constraint is the task that appears most frequently. Let's say this frequency is `max_freq`.

Consider the most frequent task, say 'A'. To satisfy the cooldown `n`, the schedule for 'A's must look like `A, ..., A, ..., A`. There are `max_freq - 1` intervals between the `max_freq` occurrences of 'A'. Each of these intervals must be at least `n` slots long. This structure forms `max_freq - 1` 'frames', each of size `n+1` (one task + `n` cooldown slots). The total time for these frames is `(max_freq - 1) * (n + 1)`.

After these frames, we have the last occurrences of the most frequent tasks. If there are `k` tasks with `max_freq`, these `k` tasks will form the final part of the schedule. This adds `k` to the time. So, the total time dictated by this structure is `(max_freq - 1) * (n + 1) + k`.

This formula calculates the length assuming idle slots are necessary. However, if we have a large variety of tasks, we might be able to fill all slots without any idling. In that case, the total time is simply the total number of tasks. Therefore, the minimum time required is the larger of these two values.

```java
import java.util.Arrays;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        if (n == 0) {
            return tasks.length;
        }
        
        int[] counts = new int[26];
        for (char task : tasks) {
            counts[task - 'A']++;
        }
        
        // Find the maximum frequency
        int max_freq = 0;
        for (int count : counts) {
            max_freq = Math.max(max_freq, count);
        }
        
        // Count how many tasks have the max frequency
        int k = 0;
        for (int count : counts) {
            if (count == max_freq) {
                k++;
            }
        }
        
        // Calculate time based on idle slots determined by max_freq task
        int time = (max_freq - 1) * (n + 1) + k;
        
        // The result is the maximum of time with idles and total number of tasks
        return Math.max(tasks.length, time);
    }
}
```
### Algorithm
- First, handle the edge case where `n = 0`. In this case, no cooling is needed, so the time is simply the total number of tasks.
- Count the frequencies of all tasks using an array of size 26.
- Find the maximum frequency, `max_freq`, among all tasks.
- Count the number of tasks, `k`, that have this `max_freq`.
- The schedule is constrained by the most frequent task. It will form `max_freq - 1` full blocks of `n+1` slots. The total time for these is `(max_freq - 1) * (n + 1)`.
- The last block will contain the final occurrences of the `k` most frequent tasks. So, we add `k` to the time.
- This gives a potential time of `(max_freq - 1) * (n + 1) + k`.
- However, if there are many different tasks, it's possible to schedule them without any idle time. In this case, the total time is simply `tasks.length`.
- The final answer is the maximum of these two values: `max(tasks.length, (max_freq - 1) * (n + 1) + k)`.

# Solutions
### Java

```java
class Solution {
public
  int leastInterval(char[] tasks, int n) {
    int[] cnt = new int[26];
    int x = 0;
    for (char c : tasks) {
      c -= 'A';
      ++cnt[c];
      x = Math.max(x, cnt[c]);
    }
    int s = 0;
    for (int v : cnt) {
      if (v == x) {
        ++s;
      }
    }
    return Math.max(tasks.length, (x - 1) * (n + 1) + s);
  }
}

```

### CSharp

```csharp
public class Solution {
    public int LeastInterval(char[] tasks, int n) {
        int[] cnt = new int[26];
        int x = 0;
        foreach(char c in tasks) {
            cnt[c - 'A']++;
            x = Math.Max(x, cnt[c - 'A']);
        }
        int s = 0;
        foreach(int v in cnt) {
            s = v == x ? s + 1 : s;
        }
        return Math.Max(tasks.Length, (x - 1) * (n + 1) + s);
    }
}
```

### Python

```python
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int: cnt = Counter(tasks) x = max(cnt . values()) s = sum(v == x for v in cnt . values()) return max(len(tasks), (x - 1) * (n + 1) + s)

```

### CPP

```cpp
class Solution {
public:
  int leastInterval(vector<char> &tasks, int n) {
    vector<int> cnt(26);
    int x = 0;
    for (char c : tasks) {
      c -= 'A';
      ++cnt[c];
      x = max(x, cnt[c]);
    }
    int s = 0;
    for (int v : cnt) {
      s += v == x;
    }
    return max((int)tasks.size(), (x - 1) * (n + 1) + s);
  }
};

```