2365. Task Scheduler II

SourceBiweekly Contest 84 Q3DifficultyMediumRating1622

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 \(\textit{day}\) to record the next time each task can be executed. Initially, all values in \(\textit{day}\) are \(0\). We use a variable \(\textit{ans}\) to record the current time.

We iterate through the array \(\textit{tasks}\). For each task \(\textit{task}\), we increment the current time \(\textit{ans}\) by one, indicating that one day has passed since the last task execution. If \(\textit{day}[\textit{task}] > \textit{ans}\) at this time, it means that task \(\textit{task}\) can only be executed on the \(\textit{day}[\textit{task}]\) day. Therefore, we update the current time \(\textit{ans} = \max(\textit{ans}, \textit{day}[\textit{task}])\). Then we update the value of \(\textit{day}[\textit{task}]\) to \(\textit{ans} + \textit{space} + 1\), indicating that the next time task \(\textit{task}\) can be executed is at \(\textit{ans} + \textit{space} + 1\).

After the iteration, we return \(\textit{ans}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{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