Skip to content

2365. Task Scheduler II

Description

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 <= 105
  • 1 <= tasks[i] <= 109
  • 1 <= space <= tasks.length

Solutions

Solution 1: 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\).

1
2
3
4
5
6
7
8
9
class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        day = defaultdict(int)
        ans = 0
        for task in tasks:
            ans += 1
            ans = max(ans, day[task])
            day[task] = ans + space + 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public long taskSchedulerII(int[] tasks, int space) {
        Map<Integer, Long> day = new HashMap<>();
        long ans = 0;
        for (int task : tasks) {
            ++ans;
            ans = Math.max(ans, day.getOrDefault(task, 0L));
            day.put(task, ans + space + 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    long long taskSchedulerII(vector<int>& tasks, int space) {
        unordered_map<int, long long> day;
        long long ans = 0;
        for (int& task : tasks) {
            ++ans;
            ans = max(ans, day[task]);
            day[task] = ans + space + 1;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

Comments