Problem Description

You have an array of tasks that must be completed in the exact order they appear. Each task has a type (represented by a positive integer), and there's a cooling period between tasks of the same type.

Given:

• A 0-indexed array tasks where tasks[i] represents the type of the i-th task
• A positive integer space representing the minimum number of days that must pass after completing a task before you can do another task of the same type

Each day you can either:

1. Complete the next task in the array (in order)
2. Take a break (do nothing)

The goal is to find the minimum number of days needed to complete all tasks while respecting the cooling period constraint.

For example, if space = 2 and you complete a task of type 1 on day 1, the earliest you can do another task of type 1 is on day 4 (with at least 2 days in between).

The solution uses a hash table to track when each task type can next be executed. As we process each task:

• We move forward at least one day (ans += 1)
• If the task type has a cooling period restriction, we may need to wait longer (take breaks) until that task type is available
• We update ans to be the maximum of the current day or the earliest day this task type can be executed
• We record that the next time this task type can be done is ans + space + 1 days

The final answer is the total number of days needed to complete all tasks in order.

Intuition

The key insight is that we need to track when each task type becomes available again after being executed. Since tasks must be completed in order, we're essentially simulating the process day by day.

Think of it this way: when we complete a task of type X, we create a "cooldown window" where we cannot do another task of type X for space days. If we encounter another task of type X during this cooldown, we must wait (take breaks) until the cooldown expires.

The natural approach is to maintain a record of "when can I next execute each task type?" For each task type, we store the earliest day it can be executed again.

As we process each task in order:

1. At minimum, we need one more day than the previous task (since we do one task per day)
2. But if this task type is still in cooldown, we might need to wait longer

The clever part is using max(current_day, cooldown_end_day) to handle both cases - either we can do the task immediately (current day is later than cooldown), or we need to wait until the cooldown ends.

After executing a task on day ans, that task type cannot be done again until day ans + space + 1. The +1 is crucial because if we do a task on day 5 with space = 2, we need 2 full days of gap (days 6 and 7), so the earliest we can do it again is day 8, which is 5 + 2 + 1.

This greedy approach works because we always complete tasks as early as possible while respecting constraints, and since tasks must be done in order, there's no benefit to delaying a task unnecessarily.

Solution Approach

We use a hash table combined with simulation to solve this problem efficiently.

Data Structure:

• Hash table day: Maps each task type to the next available day it can be executed. Initially, all values are 0 (any task can be done from day 0 onwards).
• Variable ans: Tracks the current day/time.

Algorithm Steps:

1. Initialize the tracking structures:

   • Create a defaultdict(int) named day to store the next available day for each task type
   • Set ans = 0 to represent the current time

2. Process each task in order: For each task in the tasks array:

   a. Advance time by at least one day:

   ans += 1

   This represents doing the current task on the next available day.

   b. Check cooling period constraint:

   ans = max(ans, day[task])

   If day[task] > ans, it means this task type is still in cooldown. We must wait until day[task] to execute it. Otherwise, we can execute it on the current day ans.

   c. Update the next available time for this task type:

   day[task] = ans + space + 1

   After executing the task on day ans, the next time we can execute the same task type is ans + space + 1 (current day + cooling period + 1).

3. Return the result: After processing all tasks, ans contains the total number of days needed.

Why this works:

• We process tasks in the required order (no reordering allowed)
• For each task, we find the earliest possible day to execute it
• The max operation ensures we respect both the sequential constraint (at least one day after the previous task) and the cooling period constraint
• By updating day[task] after each execution, we maintain accurate cooldown information for future tasks of the same type

Time Complexity: O(n) where n is the number of tasks Space Complexity: O(m) where m is the number of unique task types

Example Walkthrough

Let's walk through an example with tasks = [1, 1, 2, 1] and space = 2.

Initial State:

• day = {} (empty hash table, all task types can be executed from day 0)
• ans = 0 (starting at day 0)

Processing Task 0 (type 1):

• Advance time: ans = 0 + 1 = 1
• Check cooling constraint: ans = max(1, day[1]) = max(1, 0) = 1
• Execute task type 1 on day 1
• Update next available: day[1] = 1 + 2 + 1 = 4
• State: day = {1: 4}, ans = 1

Processing Task 1 (type 1):

• Advance time: ans = 1 + 1 = 2
• Check cooling constraint: ans = max(2, day[1]) = max(2, 4) = 4
• Must wait until day 4 to execute task type 1 again (days 2, 3 are breaks)
• Update next available: day[1] = 4 + 2 + 1 = 7
• State: day = {1: 7}, ans = 4

Processing Task 2 (type 2):

• Advance time: ans = 4 + 1 = 5
• Check cooling constraint: ans = max(5, day[2]) = max(5, 0) = 5
• Execute task type 2 on day 5 (no cooling needed, first time doing type 2)
• Update next available: day[2] = 5 + 2 + 1 = 8
• State: day = {1: 7, 2: 8}, ans = 5

Processing Task 3 (type 1):

• Advance time: ans = 5 + 1 = 6
• Check cooling constraint: ans = max(6, day[1]) = max(6, 7) = 7
• Must wait until day 7 to execute task type 1 again
• Update next available: day[1] = 7 + 2 + 1 = 10
• State: day = {1: 10, 2: 8}, ans = 7

Final Result: 7 days

The schedule would be:

• Day 1: Task 0 (type 1)
• Day 2-3: Break (cooling period for type 1)
• Day 4: Task 1 (type 1)
• Day 5: Task 2 (type 2)
• Day 6: Break (cooling period for type 1)
• Day 7: Task 3 (type 1)

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array tasks. The algorithm iterates through the tasks array exactly once, and for each task, it performs constant-time operations: accessing and updating a dictionary entry, comparing two values with max(), and performing basic arithmetic operations.

The space complexity is O(n) in the worst case, where n is the length of the array tasks. This occurs when all tasks in the array are unique, requiring the day dictionary to store up to n different task types as keys with their corresponding values. In the best case where all tasks are identical, the space complexity would be O(1), but we consider the worst-case scenario for space complexity analysis.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Off-by-One Error in Cooling Period Calculation

The Problem: A common mistake is incorrectly calculating when a task type becomes available again. Developers often write:

next_available_day[task] = current_day + space  # WRONG!

This incorrectly allows the same task type to be executed with only space-1 days in between, violating the constraint.

Why it happens: The confusion arises from misunderstanding what "space" represents. If space = 2, there must be at least 2 days between tasks of the same type, not including the days when the tasks are executed.

Example of the error:

• Task type 1 executed on day 1
• With incorrect formula: next available = 1 + 2 = day 3
• This gives only 1 day of gap (day 2), not 2 days

The Correct Solution:

next_available_day[task] = current_day + space + 1  # CORRECT!

This ensures exactly space days between task executions:

• Task executed on day 1
• Next available = 1 + 2 + 1 = day 4
• Gap days: day 2 and day 3 (exactly 2 days)

Pitfall 2: Forgetting to Increment the Day Counter

The Problem: Some implementations forget to always move forward in time, leading to incorrect results:

# WRONG approach
for task in tasks:
    current_day = max(current_day, next_available_day[task])  # Missing increment!
    next_available_day[task] = current_day + space + 1

Why it fails: Without incrementing current_day first, multiple consecutive tasks of different types could be assigned to the same day, which violates the constraint that you can only complete one task per day.

The Correct Solution: Always increment the day counter before checking constraints:

for task in tasks:
    current_day += 1  # Always move forward at least one day
    current_day = max(current_day, next_available_day[task])
    next_available_day[task] = current_day + space + 1

Pitfall 3: Using Regular Dictionary Instead of DefaultDict

The Problem: Using a regular dictionary requires checking if a key exists before accessing it:

# More error-prone approach
next_available_day = {}
for task in tasks:
    current_day += 1
    if task in next_available_day:  # Extra check needed
        current_day = max(current_day, next_available_day[task])
    next_available_day[task] = current_day + space + 1

Why it's problematic: While not incorrect, this approach adds unnecessary complexity and potential for bugs if you forget the existence check.

The Better Solution: Use defaultdict(int) which automatically returns 0 for missing keys:

next_available_day = defaultdict(int)  # Cleaner and safer

This simplifies the code and eliminates a potential source of KeyError exceptions.