Task Scheduler II
Task Scheduler II is a medium arrays & hashing problem solved with the hashing pattern.
The best approach, optimal (jump straight to the earliest allowed day), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (advance one day at a time) up.
Problem
You must finish a list of tasks in the given order. tasks[i] is the type of the i-th task. Each day you either complete the next task or take a break.
After a task of some type is done, at least space days must pass before another task of the same type can be done. Return the minimum number of days needed to finish all tasks.
Examples
Example 1
- Input
tasks = [2, 3, 2, 2], space = 2- Output
7- Why
- Day 1: type 2. Day 2: type 3. Day 3 must be a break (type 2 ran on day 1). Day 4: type 2. Days 5 and 6 are breaks, day 7: type 2.
Example 2
- Input
tasks = [5, 6, 7], space = 10- Output
3- Why
- All types are different, so no waiting is ever needed.
Example 3
- Input
tasks = [1, 1, 1], space = 1- Output
5- Why
- The same type runs on days 1, 3 and 5, with one break day between each pair.
Constraints
1 <= tasks.length <= 10^51 <= tasks[i] <= 10^91 <= space <= tasks.length
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (advance one day at a time) | O(n · space) | O(n) |
| Optimal (jump straight to the earliest allowed day) | O(n) | O(n) |
1Brute force (advance one day at a time)
O(n · space)Each task can wait through up to space break days one by one.O(n)The map holds up to n task types.Simulate the calendar. For each task move to the next day, and while that day is still too close to the last run of the same type, take a break and move one more day.
- day = 0; last = map from type to the day it last ran.
- For each task: day++, then while the type ran before and day - last[type] <= space, day++.
- Record last[type] = day. Return day.
class Solution {
public long taskSchedulerII(int[] tasks, int space) {
Map<Integer, Long> last = new HashMap<>();
long day = 0;
for (int t : tasks) {
day++;
while (last.containsKey(t) && day - last.get(t) <= space) day++;
last.put(t, day);
}
return day;
}
}class Solution:
def taskSchedulerII(self, tasks: List[int], space: int) -> int:
last = {}
day = 0
for t in tasks:
day += 1
while t in last and day - last[t] <= space:
day += 1
last[t] = day
return dayclass Solution {
public:
long long taskSchedulerII(vector<int>& tasks, int space) {
unordered_map<int, long long> last;
long long day = 0;
for (int t : tasks) {
day++;
while (last.count(t) && day - last[t] <= space) day++;
last[t] = day;
}
return day;
}
};function taskSchedulerII(tasks, space) {
const last = new Map();
let day = 0;
for (const t of tasks) {
day++;
while (last.has(t) && day - last.get(t) <= space) day++;
last.set(t, day);
}
return day;
}2Optimal (jump straight to the earliest allowed day)
O(n)One O(1) map lookup and update per task.O(n)The map holds up to n task types.Instead of waiting one day at a time, compute the earliest legal day directly: the day after the previous task, or the day after the cooldown of this type ends, whichever is later.
- day = 0; last = map from type to its last day.
- For each task t: day = day + 1; if t ran before, day = max(day, last[t] + space + 1).
- Record last[t] = day. Return day.
class Solution {
public long 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 = Math.max(day, prev + space + 1);
last.put(t, day);
}
return day;
}
}class Solution:
def taskSchedulerII(self, tasks: List[int], space: int) -> int:
last = {}
day = 0
for t in tasks:
day += 1
if t in last:
day = max(day, last[t] + space + 1)
last[t] = day
return dayclass Solution {
public:
long long 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 = max(day, it->second + space + 1);
last[t] = day;
}
return day;
}
};function taskSchedulerII(tasks, space) {
const last = new Map();
let day = 0;
for (const t of tasks) {
day++;
if (last.has(t)) day = Math.max(day, last.get(t) + space + 1);
last.set(t, day);
}
return day;
}Edge cases to test
- A single task (answer 1)
- All tasks distinct (answer n)
- All tasks the same type (answer 1 + (n - 1) · (space + 1))
- 10^5 equal tasks with space 10^5 need about 10^10 days, beyond the 32-bit range, so use a 64-bit counter
Hints
Hint 1
For each task type you only need the day it last ran.
Hint 2
Task i cannot run before day last[type] + space + 1, and also not before the day after the previous task. Take the larger one.
FAQ
What is the best time complexity for Task Scheduler II?
Optimal (jump straight to the earliest allowed day) runs in O(n) time and O(n) extra space. One O(1) map lookup and update per task.
Which pattern does Task Scheduler II use?
It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.
Is there a brute force solution for Task Scheduler II?
Yes. Brute force (advance one day at a time) takes O(n · space) time and O(n) space. Simulate the calendar.
Which edge cases should I test for Task Scheduler II?
A single task (answer 1); All tasks distinct (answer n); All tasks the same type (answer 1 + (n - 1) · (space + 1)); 10^5 equal tasks with space 10^5 need about 10^10 days, beyond the 32-bit range, so use a 64-bit counter.