Watch 7 video solutions for Task Scheduler II, a medium level problem involving Array, Hash Table, Simulation. This walkthrough by codingMohan has 2,680 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |