Task Scheduler II

Medium Arrays & Hashing Hashing Original on LeetCode

Reported atCoinbaseRubrik

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

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(n · space)Each task can wait through up to space break days one by one.
SpaceO(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.

  1. day = 0; last = map from type to the day it last ran.
  2. For each task: day++, then while the type ran before and day - last[type] <= space, day++.
  3. 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;
    }
}

2Optimal (jump straight to the earliest allowed day)

TimeO(n)One O(1) map lookup and update per task.
SpaceO(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.

  1. day = 0; last = map from type to its last day.
  2. For each task t: day = day + 1; if t ran before, day = max(day, last[t] + space + 1).
  3. 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;
    }
}

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.