Task Scheduler II

Problem 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 i-th 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.

Key Insights

• Tasks must be completed in the order they are given.
• After completing a task of a certain type, we must wait for a specified number of days (space) before completing another task of the same type.
• We can use a hash table (or dictionary) to keep track of the last completed day for each task type.
• We need to simulate the task completion while respecting the space constraint.

Space and Time Complexity

Time Complexity: O(n), where n is the number of tasks, as we iterate through the tasks array once. Space Complexity: O(m), where m is the number of unique task types, as we store the last completed day for each task type.

Solution

To solve the problem, we can use a hash map (or dictionary) to keep track of the last day a task of a certain type was completed. For each task in the tasks array, we check if we can complete it on the current day or if we need to wait. We maintain a variable to count the total number of days taken. If the last completion day for a task is less than space days ago, we can complete the task; otherwise, we need to take breaks until we can complete it.

Code Solutions