<p>You are given a <strong>0-indexed</strong> array of positive integers <code>tasks</code>, representing tasks that need to be completed <strong>in order</strong>, where <code>tasks[i]</code> represents the <strong>type</strong> of the <code>i<sup>th</sup></code> task.</p>

<p>You are also given a positive integer <code>space</code>, which represents the <strong>minimum</strong> number of days that must pass <strong>after</strong> the completion of a task before another task of the <strong>same</strong> type can be performed.</p>

<p>Each day, until all tasks have been completed, you must either:</p>

<ul>
	<li>Complete the next task from <code>tasks</code>, or</li>
	<li>Take a break.</li>
</ul>

<p>Return<em> the <strong>minimum</strong> number of days needed to complete all tasks</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> tasks = [1,2,1,2,3,1], space = 3
<strong>Output:</strong> 9
<strong>Explanation:</strong>
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> tasks = [5,8,8,5], space = 2
<strong>Output:</strong> 6
<strong>Explanation:</strong>
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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= tasks.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= tasks[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= space &lt;= tasks.length</code></li>
</ul>

"""
To solve the problem of determining the minimum number of days needed to complete all tasks with a given spacing constraint, we can use a hash map (or dictionary) to keep track of when a task of each type was last completed. Using this information, we can decide whether we can perform the next task immediately or if we need to take a break.

Here's a step-by-step approach:

Initialize Variables:

A dictionary last_completed to store the last completion day for each type of task.
A counter current_day to keep track of the total days passed.
Iterate Over Tasks:

For each task in the tasks list, check when the same type of task was last completed.
If the task can be performed today (based on the space constraint and its last completion day), update its last completion day in the dictionary.
If not, calculate the necessary break days before this task can be performed, then update the last completion day.
Update Days:

For each task, update current_day accordingly, whether the task is performed directly or after a break.
This algorithm ensures that each task is scheduled as soon as possible but respects the cooling period defined by space.

Explanation:
Dictionary Use: The dictionary last_completed maps each task type to the last day (zero-based index) it was completed. It helps determine when a task can be next scheduled.
Day Calculation: The current_day is incremented based on whether a task can be performed on the next day or after a calculated break.
Condition Check: The condition if task in last_completed and current_day - last_completed[task] <= space checks if the same type of task was performed recently (within the space days). If true, it calculates the next possible day to perform the task.
Time Complexity: The algorithm processes each task exactly once, giving it an O(n) time complexity, where n is the number of tasks. The space complexity is also O(n) in the worst case, where each task is of a different type.


"""

class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        
        last_completed = {}  # Stores the last completion day for each task type
        current_day = 0      # Tracks the current day (0-indexed for simplicity)
        
        for task in tasks:
            if task in last_completed and current_day - last_completed[task] <= space:
                # Need to take a break if the current day is within the 'space' window of the last completion
                next_possible_day = last_completed[task] + space + 1
                current_day = next_possible_day
            else:
                # No need for a break, perform the task the next day
                current_day += 1
            
            # Update the last completed day for the current task
            last_completed[task] = current_day

        return current_day



663