Task Scheduler II — Solution in Python, Java & C++
Task Scheduler II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Task Scheduler II is a medium coding problem on arrays, hash table and simulation, asked in Amazon, Google and Rubrik interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Simulation
- Asked at: Amazon, Google, Rubrik
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You must complete the tasks in the order given: tasks[i] is the type of the i-th task. Each day, starting from day 1, you either complete the next task or take a break.
After completing a task of some type, you must wait at least space days before completing another task of the same type — that is, if a task of type t was done on day d, the next task of type t can be done on day d + space + 1 at the earliest.
Return the minimum number of days needed to complete all tasks.
Note: the original problem allows 10^5 tasks and returns a 64-bit day count; here tasks.length <= 10^4, so the answer always fits in a 32-bit integer.
Example 1
Input: tasks = [2,5,2,7,5,2], space = 2
Output: 7
Explanation: Days 1–2 run types 2 and 5. Type 2 is next but was done on day 1, so day 3 is a break and it runs on day 4. Then 7, 5 and 2 run on days 5, 6 and 7.
Example 2
Input: tasks = [4,4,4], space = 3
Output: 9
Explanation: The type-4 tasks run on days 1, 5 and 9.
Example 3
Input: tasks = [1,2,3], space = 1
Output: 3
Constraints
1 <= tasks.length <= 10^41 <= tasks[i] <= 10^91 <= space <= tasks.length
Hints for Task Scheduler II
Hint 1
Simulating break days one at a time can take
spacesteps per task.Hint 2
For each task type, remember the day it was last completed.
Hint 3
When the next task's type is not ready yet, jump the clock straight to
last + space + 1.
How to solve Task Scheduler II
The order is fixed, so the only freedom is how many breaks to take — and the fewest breaks means running each task on the earliest day its type allows. Jumping the clock over the breaks makes it one O(1) step per task.
Approach
- Keep
day = 0and a maplastfrom task type to the day it last ran. - For each task: advance
dayby one. - If its type ran before and
day - last[type] <= space, setday = last[type] + space + 1. - Record
last[type] = day. After the loop,dayis the answer.
Why it works
Running a task as early as possible never hurts later tasks: the following task's earliest day is a non-decreasing function of this task's day, and the cooldown of its own type only gets looser the earlier this one ran. So by induction the greedy day for every task is the minimum achievable, and in particular for the last one.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The gap is
spacefull days between two runs, so the earliest next day islast + space + 1, notlast + space. - The day count grows to about
n * space; with the original limits it needs 64 bits. - Different types never block each other — only the same type does.
Reference solution
Python
from typing import List
def taskSchedulerII(tasks: List[int], space: int) -> int:
last = {}
day = 0
for t in tasks:
day += 1
if t in last and day - last[t] <= space:
day = last[t] + space + 1
last[t] = day
return dayJava
public static int taskSchedulerII(int[] tasks, int space) {
Map<Integer, Long> last = new HashMap<>();
long day = 0;
for (int t : tasks) {
day++;
Long prev = last.get(t);
if (prev != null && day - prev <= space) day = prev + space + 1;
last.put(t, day);
}
return (int) day;
}C++
int taskSchedulerII(vector<int>& tasks, int space) {
unordered_map<int, long long> last;
long long day = 0;
for (int t : tasks) {
day++;
auto it = last.find(t);
if (it != last.end() && day - it->second <= space) day = it->second + space + 1;
last[t] = day;
}
return (int)day;
}JavaScript
var taskSchedulerII = function(tasks, space) {
var last = new Map();
var day = 0;
for (var i = 0; i < tasks.length; i++) {
var t = tasks[i];
day++;
var prev = last.get(t);
if (prev !== undefined && day - prev <= space) day = prev + space + 1;
last.set(t, day);
}
return day;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets