Task Scheduler II

Medium
1158.

Task Scheduler II

Task Scheduler II is a medium coding problem on arrays, hash table and simulation, asked in Amazon, Google and Rubrik interviews.

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^4
  • 1 <= tasks[i] <= 10^9
  • 1 <= space <= tasks.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} tasks
 * @param {number} space
 * @return {number}
 */
var taskSchedulerII = function(tasks, space) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 1 <= tasks[i] <= 10^9
  • 1 <= space <= tasks.length

Hints for Task Scheduler II

  1. Hint 1

    Simulating break days one at a time can take space steps per task.

  2. Hint 2

    For each task type, remember the day it was last completed.

  3. 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

  1. Keep day = 0 and a map last from task type to the day it last ran.
  2. For each task: advance day by one.
  3. If its type ran before and day - last[type] <= space, set day = last[type] + space + 1.
  4. Record last[type] = day. After the loop, day is 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 space full days between two runs, so the earliest next day is last + space + 1, not last + 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 day

Java

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