Task Scheduler II
MedPrompt
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:
- Complete the next task from
tasks, or - Take a break.
Return 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.length
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the process day by day. We maintain the current day and the index of the next task to be completed. In a loop, we advance one day at a time. On each day, we check if the cooldown period for the next task has passed. If it has, we "complete" the task, update its last completion day, and move to the next task in the input array. If not, we "take a break", meaning we simply advance to the next day without completing a task. This continues until all tasks are completed.
Algorithm
- Initialize
currentDay = 1,taskIndex = 0. - Initialize a hash map
lastCompletionDayto storetask_type -> completion_day. - While
taskIndex < tasks.length:- Let
task = tasks[taskIndex]. - Check if
taskcan be performed oncurrentDay. The condition is that either the task has never been performed, orcurrentDay >= lastCompletionDay.get(task) + space + 1. - If the task can be performed:
- Update
lastCompletionDay.put(task, currentDay). - Increment
taskIndex.
- Update
- Increment
currentDay.
- Let
- Return
currentDay - 1.
Walkthrough
The core idea is to mimic the real-world process. We use a variable currentDay to track the passage of time, initialized to 1, and taskIndex to point to the current task in the tasks array. A hash map, lastCompletionDay, stores the most recent day a task of a certain type was completed.
The main loop continues as long as there are tasks to be completed (taskIndex < tasks.length). Inside the loop, for the current day currentDay:
- We identify the next task:
task = tasks[taskIndex]. - We check if this task type is in our
lastCompletionDaymap. - If it's a new task type or if the cooldown condition (
currentDay >= lastCompletionDay.get(task) + space + 1) is met, we can perform the task.- We update
lastCompletionDay.put(task, currentDay). - We advance to the next task by incrementing
taskIndex.
- We update
- If the cooldown is not over, we do nothing but let the day pass, effectively taking a break.
- In either case, we increment
currentDayto move to the next day.
The loop terminates when all tasks are done. The total number of days is currentDay - 1 because currentDay is incremented one last time after the last task is scheduled.
import java.util.HashMap;import java.util.Map; class Solution { public long taskSchedulerII(int[] tasks, int space) { Map<Integer, Long> lastCompletionDay = new HashMap<>(); long currentDay = 1; int taskIndex = 0; while (taskIndex < tasks.length) { int currentTaskType = tasks[taskIndex]; if (!lastCompletionDay.containsKey(currentTaskType) || currentDay >= lastCompletionDay.get(currentTaskType) + space + 1) { // Can perform the task lastCompletionDay.put(currentTaskType, currentDay); taskIndex++; } // Whether we did a task or took a break, the day passes. currentDay++; } return currentDay - 1; }}Complexity
Time
O(D), where D is the total number of days needed. In the worst case, D can be on the order of `N * space`, where N is the number of tasks. Given the constraints (`N <= 10^5`, `space <= 10^5`), this can be up to `10^10`, which is too slow.
Space
O(U), where U is the number of unique task types. In the worst case, all tasks are unique, so the complexity is O(N), where N is the total number of tasks.
Trade-offs
Pros
Conceptually simple and directly follows the problem description.
Easy to understand and implement.
Cons
Highly inefficient for large values of
spaceortasks.length.Likely to result in a 'Time Limit Exceeded' error on most platforms due to its high time complexity in the worst case.
Instead of simulating day by day, this optimal approach processes tasks one by one and directly calculates the day on which each task will be completed. We maintain a currentDay counter. For each task, we determine the earliest day it can be performed based on the cooldown from its previous execution. If the current day is too early, we jump forward in time by taking the necessary number of break days, which is much more efficient than iterating through them.
Algorithm
- Initialize
currentDay = 0L. - Initialize a hash map
lastDayto storetask_type -> completion_day. - For each
taskin thetasksarray:- Increment
currentDayto signify moving to the next available day. - If
taskexists inlastDay:- Let
lastCompletionDay = lastDay.get(task). - Calculate the earliest possible day for the current task:
earliestDay = lastCompletionDay + space + 1. - Update
currentDay = Math.max(currentDay, earliestDay). This step effectively jumps over any required break days.
- Let
- Update
lastDay.put(task, currentDay)with the day the task is completed.
- Increment
- Return
currentDay.
Walkthrough
This approach iterates through the tasks array just once. We use a variable currentDay to track the total days elapsed, and a hash map lastDay to store the completion day for each task type.
For each task in the input array:
- We optimistically advance to the next day by incrementing
currentDay. - We check if we have performed this task type before by looking it up in the
lastDaymap. - If we have, we retrieve its last completion day,
lastCompletionDay. The rule states we must waitspacedays, so the current task cannot be done before daylastCompletionDay + space + 1. - We then take the maximum of our current
currentDayand this calculatedearliestDay. This ensures the cooldown is respected. IfcurrentDaywas already past theearliestDay, no breaks are needed. If not,currentDayis updated toearliestDay, effectively fast-forwarding through the break period. - Finally, we record the completion day of the current task in the
lastDaymap by storing the finalcurrentDayvalue.
After the loop finishes, currentDay holds the minimum number of days to complete all tasks.
import java.util.HashMap;import java.util.Map; class Solution { public long taskSchedulerII(int[] tasks, int space) { // Map to store the last day a task of a certain type was completed. // Key: task type, Value: day of completion. Map<Integer, Long> lastDay = new HashMap<>(); long currentDay = 0; for (int task : tasks) { // Move to the next day to attempt the current task. currentDay++; if (lastDay.containsKey(task)) { long lastCompletionDay = lastDay.get(task); // The earliest this task can be done again is 'space' days after the last one. // So, it must be on or after day 'lastCompletionDay + space + 1'. long earliestNextDay = lastCompletionDay + space + 1; // If the current day is before the earliest possible day, we must wait. // We jump time to the earliest possible day. currentDay = Math.max(currentDay, earliestNextDay); } // Update the last completion day for the current task type. lastDay.put(task, currentDay); } return currentDay; }}Complexity
Time
O(N), where N is the number of tasks. We iterate through the `tasks` array once, and each hash map operation (get, put) takes O(1) time on average.
Space
O(U), where U is the number of unique task types. In the worst case, U can be equal to N, making the space complexity O(N).
Trade-offs
Pros
Highly efficient with a linear time complexity, making it suitable for large inputs.
Directly calculates the result without unnecessary simulation steps.
Handles large values of
spaceeffectively.
Cons
Requires careful handling of
longdata type to avoid integer overflow for the day counter.
Solutions
Solution
class Solution {public long taskSchedulerII(int[] tasks, int space) { Map<Integer, Long> day = new HashMap<>(); long ans = 0; for (int task : tasks) { ++ans; ans = Math.max(ans, day.getOrDefault(task, 0L)); day.put(task, ans + space + 1); } return ans; }}class Solution {public: long long taskSchedulerII(vector<int> &tasks, int space) { unordered_map<int, long long> day; long long ans = 0; for (int &task : tasks) { ++ans; ans = max(ans, day[task]); day[task] = ans + space + 1; } return ans; }};class Solution: def taskSchedulerII(self, tasks: List[int], space: int) -> int: day = defaultdict(int) ans = 0 for task in tasks: ans += 1 ans = max(ans, day[task]) day[task] = ans + space + 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.