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:
tasks, orReturn 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 <= 1051 <= tasks[i] <= 1091 <= space <= tasks.lengthProblem Overview: You receive an array tasks where each value represents a task type. After completing a task, you must wait space days before performing the same type again. The goal is to compute the minimum number of days required to finish all tasks while respecting this cooldown.
Approach 1: Greedy Simulation with HashMap (O(n) time, O(n) space)
This approach simulates the schedule day by day using a greedy rule: perform tasks as early as possible. Maintain a HashMap that stores the last day each task type was completed. Iterate through tasks and track the current day counter. For every task, check the previous completion day from the map. If the cooldown constraint is violated (currentDay - lastDay <= space), jump the day forward to lastDay + space + 1. Otherwise execute it immediately. Update the map with the new completion day. The key insight is that you never need to simulate idle days one by one—you jump directly to the earliest valid day. This produces an efficient linear pass using a hash lookup per task. This method relies on hash tables and straightforward simulation.
Approach 2: Index-Based Pointer Array (O(n) time, O(k) space)
If task IDs fall within a manageable numeric range, you can replace the hash map with a direct-access array indexed by task ID. Each index stores the last completion day for that task. The scheduling logic remains identical: maintain a running day pointer and jump forward when the cooldown constraint blocks execution. Direct indexing removes hash overhead and can be faster in lower-level languages such as C or C++. Space usage becomes O(k), where k is the maximum task ID. This technique is common when solving array-based problems where values can act as indices.
Recommended for interviews: The greedy HashMap simulation is the expected solution. It shows you understand how to enforce cooldown constraints while minimizing idle time. Interviewers want to see the key optimization: jumping the day pointer instead of iterating through idle days. The array-based variant is a good follow-up optimization when the task domain is small or performance matters.
This approach uses a hashmap to keep track of the last day each task type was completed. It iterates over the tasks array, and for each task, it checks the last completion day from the hashmap. If the task can be scheduled for today, it does so. Otherwise, it calculates the next available day and schedules the task on that day. The approach ensures we minimize the breaks required between repeating tasks.
This implementation declares an array to store the last completed day for each unique task type. For each task in the input array, it checks if scheduling it on the current day violates the 'space' condition and adjusts the scheduling day accordingly. The time complexity is O(N) due to linear iteration over the task array, and the space complexity is O(1) since the task types are bounded by their constraints though they appear large (supporting O(1) array for each task type).
Time Complexity: O(N), where N is the number of tasks in the input list.
Space Complexity: O(1), considering the practical constraints of task types' range.
In this approach, we utilize an array indexed by task type to record the last day each task was completed. This is possible due to the constraints that allow us to treat tasks as direct indices. Instead of using a hash map, we leverage this array, resulting in more straightforward access and potential performance improvements concerning space.
This implementation employs a pointer array, initially filled with zeroes, and indexed by task type values directly. Given each task type is a number and is constrained, this enables fast O(1) access for checking and updating their last day of completion without requiring a hashmap. This is suitable when task types are sequential within practical limits.
Time Complexity: O(N) where N is the number of tasks.
Space Complexity: Depends on the maximum task type, potentially large but practically optimized.
We can use a hash table day to record the next time each task can be executed. Initially, all values in day are 0. We use a variable ans to record the current time.
We iterate through the array tasks. For each task task, we increment the current time ans by one, indicating that one day has passed since the last task execution. If day[task] > ans at this time, it means that task task can only be executed on the day[task] day. Therefore, we update the current time ans = max(ans, day[task]). Then we update the value of day[task] to ans + space + 1, indicating that the next time task task can be executed is at ans + space + 1.
After the iteration, we return ans.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the array tasks.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Algorithm with HashMap to Track Last Completion Day | Time Complexity: O(N), where N is the number of tasks in the input list. |
| Index-Based Pointer Array with Direct Access | Time Complexity: O(N) where N is the number of tasks. |
| Hash Table + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Simulation with HashMap | O(n) | O(n) | General case when task IDs are arbitrary and need flexible lookup |
| Index-Based Pointer Array | O(n) | O(k) | When task IDs fall within a limited numeric range and faster direct indexing is possible |
Biweekly Contest 84 | 2365. Task Scheduler II • codingMohan • 2,680 views views
Watch 6 more video solutions →Practice Task Scheduler II with our built-in code editor and test cases.
Practice on FleetCode