{x}
blog image

Task Scheduler II

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 Explanation for Task Scheduler II

This problem asks to find the minimum number of days required to complete a sequence of tasks, given constraints on the minimum spacing between tasks of the same type. The optimal approach involves simulating the task completion process using a hash map (or dictionary).

Approach: Hash Table Simulation

We use a hash map (dictionary in Python) to store the last completion day for each task type. The keys are the task types (integers), and the values are the days on which the task was last completed. Initially, all task types are considered as not having been completed yet.

The simulation proceeds as follows:

  1. Initialization: Create a hash map day to store the last completion day for each task type. Initialize ans (the total number of days) to 0.

  2. Iteration: Iterate through the tasks array. For each task:

    • Increment ans (representing the current day).
    • Check if the task type is already in day. If it is, and its last completion day is later than the current day (ans), update ans to be the next available day for that task type (from the day map). This ensures the minimum spacing is maintained.
    • Update the last completion day for the current task type in the day map to ans + space + 1, where space is the minimum spacing between consecutive tasks of the same type. Adding 1 accounts for the current day.

  3. Return: After processing all tasks, ans represents the minimum number of days needed to complete all tasks, which is the solution.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the tasks array. We iterate through the array once. Hash map operations (insertion, lookup, update) take constant time on average.

  • Space Complexity: O(k), where k is the number of unique task types. In the worst case, the hash map will store the last completion day for every unique task type. In practice k is typically much smaller than n.

Code Implementations

The provided code implements this approach in several languages: Python, Java, C++, Go, and TypeScript. They all follow the same core logic:

Python:

from collections import defaultdict
 
class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        day = defaultdict(int)  # Initialize a default dictionary
        ans = 0
        for task in tasks:
            ans += 1
            ans = max(ans, day[task]) # Ensure minimum spacing
            day[task] = ans + space + 1
        return ans

The other languages use similar data structures (HashMaps, unordered_maps) to achieve the same functionality. The key is efficiently managing the last completion day for each task type to ensure the spacing constraint.