README_EN.md

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

Python3

class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        mp = {}
        ans = 0
        for v in tasks:
            ans += 1
            ans = max(ans, mp.get(v, 0))
            mp[v] = ans + space + 1
        return ans

Java

class Solution {
    public long taskSchedulerII(int[] tasks, int space) {
        Map<Integer, Long> mp = new HashMap<>();
        long ans = 0;
        for (int v : tasks) {
            ++ans;
            ans = Math.max(ans, mp.getOrDefault(v, 0L));
            mp.put(v, ans + space + 1);
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long taskSchedulerII(vector<int>& tasks, int space) {
        unordered_map<int, long long> mp;
        long long ans = 0;
        for (int v : tasks) {
            ++ans;
            if (mp.count(v)) ans = max(ans, mp[v]);
            mp[v] = ans + space + 1;
        }
        return ans;
    }
};

Go

func taskSchedulerII(tasks []int, space int) int64 {
	mp := map[int]int64{}
	var ans int64
	for _, x := range tasks {
		ans++
		if v, ok := mp[x]; ok {
			ans = max(ans, v)
		}
		mp[x] = ans + int64(space) + 1
	}
	return ans
}

func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

TypeScript

...