Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2365.html

2365. Task Scheduler II

  • Difficulty: Medium.
  • Related Topics: Array, Hash Table, Simulation.
  • Similar Questions: Task Scheduler, Maximize Distance to Closest Person, Check If All 1’s Are at Least Length K Places Away.

Problem

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

Solution (Java, C++, Python)

  • class Solution {
    public long taskSchedulerII(int[] tasks, int space) {
        long days = 0;
        space++;
        HashMap<Integer, Long> lastOccurence = new HashMap<>();
        for (int i = 0; i < tasks.length; i++) {
            if (lastOccurence.containsKey(tasks[i])) {
                long lastTimeOccurred = lastOccurence.get(tasks[i]);
                long daysDifference = days - lastTimeOccurred;
                if (daysDifference < space) {
                    days += (space - daysDifference);
                }
            }
            lastOccurence.put(tasks[i], days);
            days++;
        }
        return days;
    }
}

############

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;
    }
}

  • 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

############

# 2365. Task Scheduler II
# https://leetcode.com/problems/task-scheduler-ii/

class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        n = len(tasks)
        last = defaultdict(lambda: -1)
        day = 1
        
        for task in tasks:
            if last[task] == -1 or day > last[task] + space + 1:
                last[task] = day
            else:
                day = last[task] + space + 1
                last[task] = day
                
            day += 1
            
        return day - 1


  • 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;
    }
};

  • 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
}

  • 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;
}

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions