We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Task Scheduler II

Number: 2483

Difficulty: Medium

Paid? No

Companies: Nvidia, Amazon, DoorDash, Duolingo, Meta, Uber, Remitly

Problem Description

Given an ordered array of tasks where each task is represented by its type, and a positive integer space that represents the minimum number of days that must pass after completing a task before the same task type can be performed again, determine the minimum number of days needed to complete all tasks. Each day, you must either complete the next task in order or take a break.

Key Insights

  • Tasks must be executed in the given order.
  • When a task is scheduled, if the same type was executed recently, you may have to wait (simulate breaks) to satisfy the space requirement.
  • Use a hash table (dictionary) to track the next available day for each task type.
  • For each task, compute the day it can be executed by considering current day and the task’s availability from previous occurrences.

Space and Time Complexity

Time Complexity: O(n), where n is the number of tasks.
Space Complexity: O(u), where u is the number of unique task types.

Solution

We simulate the process of executing tasks day by day. For each task, we check if it was executed before. If so, we compare the current day with the next available day for that task type. If the current day is less than the next available day, we simulate waiting by jumping to that day. Then, update the next available day for that task type as the current day plus space plus one. This approach efficiently ensures that no subsequent task of the same type is scheduled before the required waiting period.

Code Solutions

# Python solution for Task Scheduler II

class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        # Dictionary to store the next available day for each task type
        next_available = {}
        # Current day counter, starting from day 1
        current_day = 1
        
        # Process tasks in order
        for task in tasks:
            # If this task was seen and current_day is less than when it can be performed again,
            # update current_day to that next available day.
            if task in next_available and current_day < next_available[task]:
                current_day = next_available[task]
            # Set the next available day for this task type
            next_available[task] = current_day + space + 1
            # Move to next day after processing this task
            current_day += 1
        
        # Return total days taken, subtracting 1 because current_day is incremented after the last task
        return current_day - 1
← Back to All Questions