Task Scheduler II solution and explanation
Google
6 more videos on this problem
Biweekly Contest 84 | 2365. Task Scheduler IIcodingMohan · 7:36 · 2K views
Leetcode 2365: Task Scheduler IIAlgorithms Casts · 9:50 · 1K views
2365. Task Scheduler II (Leetcode Medium)Programming Live with Larry · 9:31 · 1K views
Leetcode BiWeekly contest 84 - Medium - Task Scheduler IIPrakhar Agrawal · 8:03 · 718 views
【每日一题】LeetCode 2365. Task Scheduler IIHuifeng Guan · 6:55 · 702 views
Leetcode 2365DailyLeetcode · 6:55 · 329 views
160. LeetCode 2365. Task Scheduler II [ Javascript ]Web Fusion with Bharadwaj · 5:35 · 91 views
The problem
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
Approach overview
Problem 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 1: Greedy Algorithm with HashMap to Track Last Completion Day
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.
def min_days(tasks, space):
last_day = {}
day = 0
for task in tasks:
day += 1
if task in last_day:
if day - last_day[task] <= space:
day = last_day[task] + space + 1
last_day[task] = day
return day
if __name__ == "__main__":
tasks = [1, 2, 1, 2, 3, 1]
space = 3
print(min_days(tasks, space)) # Output: 9import java.util.HashMap;
public class TaskScheduler {
public int minDays(int[] tasks, int space) {
HashMap<Integer, Integer> lastDay = new HashMap<>();
int day = 0;
for (int task : tasks) {
day++;
if (lastDay.containsKey(task)) {
if (day - lastDay.get(task) <= space) {
day = lastDay.get(task) + space + 1;
}
}
lastDay.put(task, day);
}
return day;
}
public static void main(String[] args) {
TaskScheduler scheduler = new TaskScheduler();
int[] tasks = {1, 2, 1, 2, 3, 1};
int space = 3;
System.out.println(scheduler.minDays(tasks, space)); // Output: 9
}
}#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int minDays(vector<int>& tasks, int space) {
unordered_map<int, int> lastDay;
int day = 0;
for (int task : tasks) {
day++;
if (lastDay.count(task)) {
if (day - lastDay[task] <= space) {
day = lastDay[task] + space + 1;
}
}
lastDay[task] = day;
}
return day;
}
int main() {
vector<int> tasks = {1, 2, 1, 2, 3, 1};
int space = 3;
cout << minDays(tasks, space) << endl; // Output: 9
return 0;
}function minDays(tasks, space) {
const lastDay = new Map();
let day = 0;
for (const task of tasks) {
day++;
if (lastDay.has(task)) {
const last = lastDay.get(task);
if (day - last <= space) {
day = last + space + 1;
}
}
lastDay.set(task, day);
}
return day;
}
const tasks = [1, 2, 1, 2, 3, 1], space = 3;
console.log(minDays(tasks, space)); // Output: 9#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int minDays(int* tasks, int tasksSize, int space) {
int* lastDay = (int*)malloc(1000000001 * sizeof(int));
memset(lastDay, -1, 1000000001 * sizeof(int));
int day = 0;
for (int i = 0; i < tasksSize; ++i) {
day++;
if (lastDay[tasks[i]] != -1) {
if (day - lastDay[tasks[i]] <= space) {
day = lastDay[tasks[i]] + space + 1;
}
}
lastDay[tasks[i]] = day;
}
free(lastDay);
return day;
}
int main() {
int tasks[] = {1, 2, 1, 2, 3, 1};
int size = sizeof(tasks) / sizeof(tasks[0]);
int space = 3;
printf("%d\n", minDays(tasks, size, space)); // Output: 9
return 0;
}using System;
using System.Collections.Generic;
public class TaskScheduler {
public static int MinDays(int[] tasks, int space) {
var lastDay = new Dictionary<int, int>();
int day = 0;
foreach (var task in tasks) {
day++;
if (lastDay.ContainsKey(task)) {
if (day - lastDay[task] <= space) {
day = lastDay[task] + space + 1;
}
}
lastDay[task] = day;
}
return day;
}
public static void Main(String[] args) {
int[] tasks = {1, 2, 1, 2, 3, 1};
int space = 3;
Console.WriteLine(MinDays(tasks, space)); // Output: 9
}
}The Python solution leverages a dictionary to keep information on the last completion day of each task type. By iterating over the tasks list, it decides if it can execute the task on the current day or if it needs to push the day count forward based on the defined constraints. This approach ensures a minimal number of breaks while efficiently calculating the result in O(N) time.
Time Complexity: O(N), since it processes each task in the list once.
Space Complexity: O(N) for tracking last completion days of each task type.
Approach 2: Index-Based Pointer Array with Direct Access
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.
#include <iostream>
#include <vector>
using namespace std;
#define MAX_TYPE 1000000000
int minDays(vector<int>& tasks, int space) {
vector<int> lastDay(MAX_TYPE + 1, 0);
int day = 0;
for (int task : tasks) {
day++;
if (lastDay[task] != 0 && (day - lastDay[task]) <= space) {
day = lastDay[task] + space + 1;
}
lastDay[task] = day;
}
return day;
}
int main() {
vector<int> tasks = {5, 8, 8, 5};
int space = 2;
cout << minDays(tasks, space) << endl; // Output: 6
return 0;
}#include <stdio.h>
#include <stdlib.h>
#define MAX_TYPE 1000000000
int minDays(int* tasks, int taskSize, int space) {
int *lastDay = (int*)calloc(MAX_TYPE + 1, sizeof(int));
int day = 0;
for (int i = 0; i < taskSize; i++) {
day++;
if (lastDay[tasks[i]] > 0) {
if (day - lastDay[tasks[i]] <= space) {
day = lastDay[tasks[i]] + space + 1;
}
}
lastDay[tasks[i]] = day;
}
free(lastDay);
return day;
}
int main() {
int tasks[] = {5, 8, 8, 5};
int size = sizeof(tasks) / sizeof(tasks[0]);
int space = 2;
printf("%d\n", minDays(tasks, size, space)); // Output: 6
return 0;
}The C++ code uses a vector to track the last day each task was done, earmarked directly by task type. This allows direct array access based on the task number resulting in faster performance compared to maps. It helps minimize the breaks needed by scheduling tasks as soon as the space requirement allows.
Time Complexity: O(N).
Space Complexity: O(T), where T is constrained by the task type's maximum possible value.
Approach 3: Hash Table + Simulation
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.
function taskSchedulerII(tasks: number[], space: number): number {
const day = new Map<number, number>();
let ans = 0;
for (const task of tasks) {
++ans;
ans = Math.max(ans, day.get(task) ?? 0);
day.set(task, ans + space + 1);
}
return ans;
}func taskSchedulerII(tasks []int, space int) (ans int64) {
day := map[int]int64{}
for _, task := range tasks {
ans++
if ans < day[task] {
ans = day[task]
}
day[task] = ans + int64(space) + 1
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Algorithm with HashMap to Track Last Completion Day | Time Complexity: O(N), since it processes each task in the list once. |
| Index-Based Pointer Array with Direct Access | Time Complexity: O(N). |
| Hash Table + Simulation | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Task Scheduler II easy or hard?
Task Scheduler II is generally classified as a medium difficulty problem. The challenge lies in recognizing that you can jump the current day directly to the next valid execution time instead of simulating idle days, which keeps the algorithm linear.
Task Scheduler II Python/Java solution
Both Python and Java implementations follow the same logic: maintain a running day counter and a map from task type to last execution day. Python commonly uses a dictionary, while Java uses a HashMap. Each iteration checks cooldown and jumps the day forward if necessary.
How to solve Task Scheduler II in O(n)?
Track the current day and store the last execution day for each task in a hash map. When processing a task, check if the cooldown constraint is violated. If so, move the current day directly to lastDay + space + 1; otherwise increment normally. Update the stored day and continue through the array.
What is the best approach for Task Scheduler II?
The optimal solution uses a greedy simulation with a hash map to track the last completion day of each task. While iterating through the tasks array, maintain a current day counter and jump forward when a cooldown violation occurs. This avoids simulating idle days one by one and achieves O(n) time complexity with O(n) space.
Is Task Scheduler II asked at Google/Amazon/Meta?
Scheduling and cooldown-style problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of task scheduling, greedy scheduling, and simulation problems test understanding of constraints and efficient state tracking.
What data structure is used in Task Scheduler II?
A hash map is typically used to store the last completion day for each task type. This allows constant-time lookups when checking whether the cooldown constraint allows the task to run on the current day.
What is the time complexity of Task Scheduler II?
The optimal algorithm runs in O(n) time because each task is processed exactly once and each step performs constant-time hash lookups. Space complexity is O(n) in the worst case if all tasks are unique, since the map stores the last execution day for each task type.