2365

2365. Task Scheduler II (Medium)

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

Companies: Facebook

Related Topics:
Array, Hash Table, Simulation

Similar Questions:

• Task Scheduler (Medium)
• Maximize Distance to Closest Person (Medium)
• Check If All 1's Are at Least Length K Places Away (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/task-scheduler-ii
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(T) where T is the number of unique tasks
class Solution {
public:
    long long taskSchedulerII(vector<int>& A, int space) {
        long long i = 0, N = A.size();
        unordered_map<int, long long> prev; // task ID -> previous occurrence's index
        for (int n : A) {
            if (prev.count(n)) {
                i += max(0LL, space - i + prev[n] + 1); // currently at `i`. There are `i-prev[n]-1` space between `i` and the previous occurrence. If `i-prev[n]-1 < space`, we need to pad `space-(i-prev[n]-1)`.
            }
            prev[n] = i;
            ++i;
        }
        return i;
    }
};