LeetCode 2365 - Task Scheduler II

The problem gives us an array tasks, where each value represents a task type. The tasks must be completed strictly in the given order, which means we cannot rearrange them to optimize the schedule. We are also given an integer space.

leetcodemediumarrayhash-tablesimulation

LeetCode Problem 2365

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Simulation

Solution

Problem Understanding

The problem gives us an array tasks, where each value represents a task type. The tasks must be completed strictly in the given order, which means we cannot rearrange them to optimize the schedule.

We are also given an integer space. After completing a task of a certain type, we must wait at least space days before performing the same task type again. During those waiting days, we may either perform other tasks or take breaks.

The goal is to compute the minimum number of total days needed to complete all tasks while respecting the cooldown rule.

For example, suppose we perform task type 1 on day 2 and space = 3. The next time we are allowed to perform task type 1 is day 6, because there must be at least 3 full days between the two executions.

The constraints are important:

  • tasks.length can be as large as 10^5
  • Task values can be very large, up to 10^9
  • space can also be large

These constraints immediately tell us that simulation day by day with repeated scanning would be too slow. We need an efficient solution that processes each task in near constant time.

An important observation is that tasks must remain in order. This removes the need for advanced scheduling structures like heaps or priority queues. At every step, we only care about whether the next task can be executed immediately or whether we must jump forward in time.

Some important edge cases include:

  • Multiple consecutive identical tasks, which force many idle days
  • Very large space values
  • Arrays where all tasks are unique, meaning no waiting is ever required
  • Arrays where one task repeats frequently
  • Large task values, which means we should use a hash map instead of an array indexed by task ID

Approaches

Brute Force Approach

A straightforward simulation would process the schedule day by day.

We maintain the current day and repeatedly check whether the next task can be executed. If the cooldown condition is satisfied, we execute the task. Otherwise, we increment the day and count it as a break day.

To determine whether a task can run, we would store the last day each task type was executed.

This approach is correct because it faithfully simulates the rules exactly as described. However, it becomes inefficient when there are large gaps caused by cooldown periods. For example, if space is very large, we may spend many iterations simply incrementing the day counter one at a time.

In the worst case, the total simulated days can become much larger than the number of tasks.

Optimal Approach

The key insight is that we never need to simulate idle days individually.

Suppose we are currently on day current_day, and the next task type was last executed on day last_day.

If:

current_day - last_day <= space

then we are forced to wait. Instead of incrementing day one by one, we can jump directly to the first valid execution day.

The earliest valid day is:

last_day + space + 1

This transforms the problem into a simple linear scan with a hash map storing the last execution day for each task type.

Because every task is processed once, the solution becomes very efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(total_days) O(n) Simulates every day individually
Optimal O(n) O(n) Jumps directly to the next valid day

Algorithm Walkthrough

  1. Create a hash map called last_execution_day.

This map stores the most recent day each task type was performed. The key is the task type, and the value is the last execution day. 2. Initialize current_day = 0.

This variable tracks the current simulated day count. 3. Process tasks one by one in order.

Since the order is fixed, we simply iterate through the tasks array. 4. Increment the current day by one before attempting the task.

Each task execution consumes one day, so we first move to the next day. 5. Check whether the task has been seen before.

If the task type already exists in the hash map, retrieve its previous execution day. 6. Verify whether the cooldown requirement is satisfied.

If:

current_day - previous_day <= space

then the cooldown has not finished yet. 7. Jump directly to the earliest valid execution day.

Instead of simulating breaks individually, update:

current_day = previous_day + space + 1

This skips all unnecessary intermediate days. 8. Record the current execution day for the task.

Update the hash map so future occurrences can enforce the cooldown correctly. 9. Continue until all tasks are processed. 10. Return current_day.

After processing all tasks, this value represents the minimum total number of days needed.

Why it works

The algorithm always schedules each task on the earliest possible valid day.

If the cooldown is already satisfied, we execute immediately. Otherwise, we jump to the first legal day that satisfies the cooldown constraint.

Because tasks must remain in order, there is never a benefit to delaying a task beyond its earliest valid day. Therefore, greedily choosing the earliest valid execution day produces the minimum total schedule length.

Python Solution

from typing import List

class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        last_execution_day = {}
        current_day = 0

        for task in tasks:
            current_day += 1

            if task in last_execution_day:
                previous_day = last_execution_day[task]

                if current_day - previous_day <= space:
                    current_day = previous_day + space + 1

            last_execution_day[task] = current_day

        return current_day

The implementation follows the algorithm directly.

The dictionary last_execution_day stores the most recent execution day for each task type. Since task values can be as large as 10^9, using a dictionary is much more practical than allocating a huge array.

The variable current_day tracks the current timeline. For every task, we first assume we will execute it on the next day by incrementing current_day.

If the task has appeared before, we retrieve its previous execution day and check whether the cooldown rule is violated. If so, we jump directly to the earliest legal day using:

current_day = previous_day + space + 1

Finally, we update the task's last execution day and continue processing.

Because every task is processed exactly once, the solution runs efficiently even for the maximum input size.

Go Solution

func taskSchedulerII(tasks []int, space int) int64 {
	lastExecutionDay := make(map[int]int64)
	var currentDay int64 = 0
	space64 := int64(space)

	for _, task := range tasks {
		currentDay++

		if previousDay, exists := lastExecutionDay[task]; exists {
			if currentDay-previousDay <= space64 {
				currentDay = previousDay + space64 + 1
			}
		}

		lastExecutionDay[task] = currentDay
	}

	return currentDay
}

The Go implementation mirrors the Python logic closely.

One important difference is integer handling. The function signature requires returning int64, so all day calculations are performed using int64 to avoid overflow issues when the total number of days becomes large.

Go maps are used similarly to Python dictionaries. The expression:

previousDay, exists := lastExecutionDay[task]

checks both whether the task exists and retrieves its previous execution day in a single operation.

Worked Examples

Example 1

Input:

tasks = [1,2,1,2,3,1]
space = 3
Step Task Current Day Before Fix Previous Day Adjustment Final Day Map State
1 1 1 None None 1 {1:1}
2 2 2 None None 2 {1:1, 2:2}
3 1 3 1 Jump to 5 5 {1:5, 2:2}
4 2 6 2 None 6 {1:5, 2:6}
5 3 7 None None 7 {1:5, 2:6, 3:7}
6 1 8 5 Jump to 9 9 {1:9, 2:6, 3:7}

Final answer:

9

Example 2

Input:

tasks = [5,8,8,5]
space = 2
Step Task Current Day Before Fix Previous Day Adjustment Final Day Map State
1 5 1 None None 1 {5:1}
2 8 2 None None 2 {5:1, 8:2}
3 8 3 2 Jump to 5 5 {5:1, 8:5}
4 5 6 1 None 6 {5:6, 8:5}

Final answer:

6

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each task is processed exactly once
Space O(n) The hash map may store every unique task type

The algorithm performs a single pass through the input array. Every hash map operation is expected O(1), so the total runtime is linear in the number of tasks.

The space complexity depends on the number of distinct task types. In the worst case, every task is unique, so the map stores n entries.

Test Cases

from typing import List

class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        last_execution_day = {}
        current_day = 0

        for task in tasks:
            current_day += 1

            if task in last_execution_day:
                previous_day = last_execution_day[task]

                if current_day - previous_day <= space:
                    current_day = previous_day + space + 1

            last_execution_day[task] = current_day

        return current_day

solution = Solution()

assert solution.taskSchedulerII([1, 2, 1, 2, 3, 1], 3) == 9
# Provided example with multiple cooldown jumps

assert solution.taskSchedulerII([5, 8, 8, 5], 2) == 6
# Provided example with repeated tasks

assert solution.taskSchedulerII([1, 2, 3, 4], 10) == 4
# All tasks unique, no waiting needed

assert solution.taskSchedulerII([1, 1, 1], 2) == 7
# Consecutive identical tasks

assert solution.taskSchedulerII([1], 5) == 1
# Single task

assert solution.taskSchedulerII([1, 2, 1], 1) == 3
# Cooldown already satisfied naturally

assert solution.taskSchedulerII([1, 2, 1], 2) == 4
# One idle day required

assert solution.taskSchedulerII([7, 7, 7, 7], 3) == 13
# Large repeated cooldown pattern

assert solution.taskSchedulerII([1, 2, 3, 1, 2, 3], 2) == 6
# Repeated tasks but naturally spaced enough

assert solution.taskSchedulerII([1000000000, 1000000000], 100000) == 100002
# Very large task values and large cooldown
Test Why
[1,2,1,2,3,1], 3 Validates the main example
[5,8,8,5], 2 Tests repeated tasks with cooldown
[1,2,3,4], 10 Ensures unique tasks need no idle days
[1,1,1], 2 Tests consecutive identical tasks
[1], 5 Smallest valid input
[1,2,1], 1 Cooldown naturally satisfied
[1,2,1], 2 Requires inserted idle time
[7,7,7,7], 3 Stress case with repeated cooldown jumps
[1,2,3,1,2,3], 2 Tasks spaced sufficiently already
[1000000000,1000000000], 100000 Large values validate hash map usage

Edge Cases

One important edge case occurs when all tasks are unique. In this situation, the cooldown rule never matters because no task type repeats. A buggy implementation might still attempt to insert unnecessary idle days. This solution handles the case naturally because tasks not present in the hash map are executed immediately.

Another important case is consecutive repeated tasks such as [1,1,1]. These inputs force the maximum number of idle days between executions. Incorrect implementations often make off by one mistakes when computing the next valid day. This solution correctly schedules the next occurrence at:

previous_day + space + 1

which guarantees exactly space days between identical tasks.

A third edge case involves very large task values like 10^9. Using an array indexed by task ID would be impossible due to memory usage. This implementation uses a hash map, which stores only task types that actually appear.

A final subtle case is when the cooldown is already satisfied naturally because of intervening tasks. For example:

tasks = [1,2,3,1]
space = 2

By the time the second 1 is processed, enough days have already passed. The algorithm correctly detects this because:

current_day - previous_day > space

so no jump is needed.