# Task Scheduler II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/task-scheduler-ii)
Canonical: https://scaleengineer.com/dsa/problems/task-scheduler-ii
**Data structures:** Array, Hash Table
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Nvidia](https://scaleengineer.com/companies/nvidia), [Remitly](https://scaleengineer.com/companies/remitly), [Duolingo](https://scaleengineer.com/companies/duolingo)
---
## Problem
You are given a **0-indexed** array of positive integers `tasks`, representing tasks that need to be completed **in order**, where `tasks[i]` represents the **type** of the `ith` task.

You are also given a positive integer `space`, which represents the **minimum** number of days that must pass **after** the completion of a task before another task of the **same** type can be performed.

Each day, until all tasks have been completed, you must either:

* Complete the next task from `tasks`, or
* Take a break.

Return _the **minimum** number of days needed to complete all tasks_.

**Example 1:**

**Input:** tasks = [1,2,1,2,3,1], space = 3
**Output:** 9
**Explanation:**
One way to complete all tasks in 9 days is as follows:
Day 1: Complete the 0th task.
Day 2: Complete the 1st task.
Day 3: Take a break.
Day 4: Take a break.
Day 5: Complete the 2nd task.
Day 6: Complete the 3rd task.
Day 7: Take a break.
Day 8: Complete the 4th task.
Day 9: Complete the 5th task.
It can be shown that the tasks cannot be completed in less than 9 days.

**Example 2:**

**Input:** tasks = [5,8,8,5], space = 2
**Output:** 6
**Explanation:**
One way to complete all tasks in 6 days is as follows:
Day 1: Complete the 0th task.
Day 2: Complete the 1st task.
Day 3: Take a break.
Day 4: Take a break.
Day 5: Complete the 2nd task.
Day 6: Complete the 3rd task.
It can be shown that the tasks cannot be completed in less than 6 days.

**Constraints:**

* `1 <= tasks.length <= 105`
* `1 <= tasks[i] <= 109`
* `1 <= space <= tasks.length`

# Approaches
## Day-by-Day Simulation
This approach simulates the process day by day. We maintain the current day and the index of the next task to be completed. In a loop, we advance one day at a time. On each day, we check if the cooldown period for the next task has passed. If it has, we "complete" the task, update its last completion day, and move to the next task in the input array. If not, we "take a break", meaning we simply advance to the next day without completing a task. This continues until all tasks are completed.
**Time:** O(D), where D is the total number of days needed. In the worst case, D can be on the order of `N * space`, where N is the number of tasks. Given the constraints (`N <= 10^5`, `space <= 10^5`), this can be up to `10^10`, which is too slow. · **Space:** O(U), where U is the number of unique task types. In the worst case, all tasks are unique, so the complexity is O(N), where N is the total number of tasks.
**Pros:** Conceptually simple and directly follows the problem description.; Easy to understand and implement.
**Cons:** Highly inefficient for large values of `space` or `tasks.length`.; Likely to result in a 'Time Limit Exceeded' error on most platforms due to its high time complexity in the worst case.
### Explanation
The core idea is to mimic the real-world process. We use a variable `currentDay` to track the passage of time, initialized to 1, and `taskIndex` to point to the current task in the `tasks` array. A hash map, `lastCompletionDay`, stores the most recent day a task of a certain type was completed.

The main loop continues as long as there are tasks to be completed (`taskIndex < tasks.length`). Inside the loop, for the current day `currentDay`:
- We identify the next task: `task = tasks[taskIndex]`.
- We check if this task type is in our `lastCompletionDay` map.
- If it's a new task type or if the cooldown condition (`currentDay >= lastCompletionDay.get(task) + space + 1`) is met, we can perform the task.
    - We update `lastCompletionDay.put(task, currentDay)`.
    - We advance to the next task by incrementing `taskIndex`.
- If the cooldown is not over, we do nothing but let the day pass, effectively taking a break.
- In either case, we increment `currentDay` to move to the next day.

The loop terminates when all tasks are done. The total number of days is `currentDay - 1` because `currentDay` is incremented one last time after the last task is scheduled.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long taskSchedulerII(int[] tasks, int space) {
        Map<Integer, Long> lastCompletionDay = new HashMap<>();
        long currentDay = 1;
        int taskIndex = 0;
        while (taskIndex < tasks.length) {
            int currentTaskType = tasks[taskIndex];
            if (!lastCompletionDay.containsKey(currentTaskType) || currentDay >= lastCompletionDay.get(currentTaskType) + space + 1) {
                // Can perform the task
                lastCompletionDay.put(currentTaskType, currentDay);
                taskIndex++;
            }
            // Whether we did a task or took a break, the day passes.
            currentDay++;
        }
        return currentDay - 1;
    }
}
```
### Algorithm
- Initialize `currentDay = 1`, `taskIndex = 0`.
- Initialize a hash map `lastCompletionDay` to store `task_type -> completion_day`.
- While `taskIndex < tasks.length`:
    - Let `task = tasks[taskIndex]`.
    - Check if `task` can be performed on `currentDay`. The condition is that either the task has never been performed, or `currentDay >= lastCompletionDay.get(task) + space + 1`.
    - If the task can be performed:
        - Update `lastCompletionDay.put(task, currentDay)`.
        - Increment `taskIndex`.
    - Increment `currentDay`.
- Return `currentDay - 1`.

## Single Pass with Direct Day Calculation
Instead of simulating day by day, this optimal approach processes tasks one by one and directly calculates the day on which each task will be completed. We maintain a `currentDay` counter. For each task, we determine the earliest day it can be performed based on the cooldown from its previous execution. If the current day is too early, we jump forward in time by taking the necessary number of break days, which is much more efficient than iterating through them.
**Time:** O(N), where N is the number of tasks. We iterate through the `tasks` array once, and each hash map operation (get, put) takes O(1) time on average. · **Space:** O(U), where U is the number of unique task types. In the worst case, U can be equal to N, making the space complexity O(N).
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Directly calculates the result without unnecessary simulation steps.; Handles large values of `space` effectively.
**Cons:** Requires careful handling of `long` data type to avoid integer overflow for the day counter.
### Explanation
This approach iterates through the `tasks` array just once. We use a variable `currentDay` to track the total days elapsed, and a hash map `lastDay` to store the completion day for each task type.

For each task in the input array:
1. We optimistically advance to the next day by incrementing `currentDay`.
2. We check if we have performed this task type before by looking it up in the `lastDay` map.
3. If we have, we retrieve its last completion day, `lastCompletionDay`. The rule states we must wait `space` days, so the current task cannot be done before day `lastCompletionDay + space + 1`.
4. We then take the maximum of our current `currentDay` and this calculated `earliestDay`. This ensures the cooldown is respected. If `currentDay` was already past the `earliestDay`, no breaks are needed. If not, `currentDay` is updated to `earliestDay`, effectively fast-forwarding through the break period.
5. Finally, we record the completion day of the current task in the `lastDay` map by storing the final `currentDay` value.

After the loop finishes, `currentDay` holds the minimum number of days to complete all tasks.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long taskSchedulerII(int[] tasks, int space) {
        // Map to store the last day a task of a certain type was completed.
        // Key: task type, Value: day of completion.
        Map<Integer, Long> lastDay = new HashMap<>();
        long currentDay = 0;

        for (int task : tasks) {
            // Move to the next day to attempt the current task.
            currentDay++;
            
            if (lastDay.containsKey(task)) {
                long lastCompletionDay = lastDay.get(task);
                // The earliest this task can be done again is 'space' days after the last one.
                // So, it must be on or after day 'lastCompletionDay + space + 1'.
                long earliestNextDay = lastCompletionDay + space + 1;
                
                // If the current day is before the earliest possible day, we must wait.
                // We jump time to the earliest possible day.
                currentDay = Math.max(currentDay, earliestNextDay);
            }
            
            // Update the last completion day for the current task type.
            lastDay.put(task, currentDay);
        }
        
        return currentDay;
    }
}
```
### Algorithm
- Initialize `currentDay = 0L`.
- Initialize a hash map `lastDay` to store `task_type -> completion_day`.
- For each `task` in the `tasks` array:
    - Increment `currentDay` to signify moving to the next available day.
    - If `task` exists in `lastDay`:
        - Let `lastCompletionDay = lastDay.get(task)`.
        - Calculate the earliest possible day for the current task: `earliestDay = lastCompletionDay + space + 1`.
        - Update `currentDay = Math.max(currentDay, earliestDay)`. This step effectively jumps over any required break days.
    - Update `lastDay.put(task, currentDay)` with the day the task is completed.
- Return `currentDay`.

# Solutions
### Java

```java
class Solution {
public
  long taskSchedulerII(int[] tasks, int space) {
    Map<Integer, Long> day = new HashMap<>();
    long ans = 0;
    for (int task : tasks) {
      ++ans;
      ans = Math.max(ans, day.getOrDefault(task, 0L));
      day.put(task, ans + space + 1);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long taskSchedulerII(vector<int> &tasks, int space) {
    unordered_map<int, long long> day;
    long long ans = 0;
    for (int &task : tasks) {
      ++ans;
      ans = max(ans, day[task]);
      day[task] = ans + space + 1;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int: day = defaultdict(int) ans = 0 for task in tasks: ans += 1 ans = max(ans, day[task]) day[task] = ans + space + 1 return ans

```