Task Scheduler II

Medium

Asked by:

273 views

Topics:

ArraysGreedy Algorithms

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.

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 <= 10⁵
1 <= tasks[i] <= 10⁹
1 <= space <= tasks.length

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the task types (values in the `tasks` array) and the cooldown period `space`?
Is the input `tasks` array guaranteed to be non-empty, and what should I return if it is empty?
If a task type appears multiple times but, due to the cooldown, some instances are skipped (e.g., in an array with only one task type and a large `space`), do I still need to process all instances?
Can I assume that both `tasks` and `space` will always be valid (e.g., `space` is non-negative) or do I need to handle potentially invalid inputs?
Could you provide a small example input and the corresponding expected output to ensure I understand the problem correctly?

Brute Force Solution

Approach

The brute force method for scheduling tasks involves simulating the process step by step, considering each task one at a time. It checks if the task is available for execution, respecting the cooling down period. We proceed until all tasks are completed, tracking the days as we go.

Here's how the algorithm would work step-by-step:

Start at day one.
Consider the first task in the list.
If the task's cooling down period hasn't finished yet (meaning we did this task too recently), then move to the next day and check again.
If the task is ready to be done, execute it and note down the day it was completed.
Move on to the next task in the list.
Repeat steps 3-5 until all tasks have been completed.
The final day we reach is the answer.

Code Implementation

def task_scheduler_brute_force(tasks, cooldown_period):
    number_of_tasks = len(tasks)
    days = 0
    completed_tasks = 0
    last_completed_day = {}

    while completed_tasks < number_of_tasks:
        days += 1
        task_index = completed_tasks

        # Check if the current task is eligible for execution
        if task_index in last_completed_day and \
           days - last_completed_day[task_index] <= cooldown_period:

            continue

        # Execute the task and update the last completed day
        last_completed_day[task_index] = days

        completed_tasks += 1

    return days

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates through each of the 'n' tasks. For each task, in the worst case, we might need to wait out the cooling down period 'k' times before the task can be executed. Therefore, the worst case scenario involves checking the cooling down period for each task, potentially 'k' times per task, where k is the cooldown period. Thus, the total number of operations is proportional to n multiplied by k, giving us a time complexity of O(n*k).

Space Complexity

O(N) – The algorithm uses a hash map (or dictionary) to store the last day each task was completed to manage the cooldown period. In the worst-case scenario, each of the N tasks requires storing its last completed day in the hash map. Therefore, the auxiliary space used by the hash map grows linearly with the number of tasks, N. This leads to an auxiliary space complexity of O(N).

Optimal Solution

Approach

The optimal solution figures out when each task can be executed, considering the cooldown period. We'll keep track of when each task *can* be done next, and update this time whenever a task is executed.

Here's how the algorithm would work step-by-step:

Imagine a timeline of when you can do each task. At the beginning, you can do any task immediately.
As you go through the tasks, check when each specific task is next available to be run, based on its cooldown.
If the current task can be done immediately, do it and update its 'next available' time by adding the cooldown period to the current time.
If the current task is not yet available (it's in cooldown), wait until it becomes available before doing it and updating its 'next available' time.
Keep track of the current time as you go. If you have to wait for a task, move the current time forward to when the task is available.
By the end, the current time represents the total time it took to complete all tasks.

Code Implementation

def task_scheduler_ii(tasks, cooldown_period):
    current_time = 0
    next_available_time = {}

    for task in tasks:
        # Check if the task is available to be executed
        if task in next_available_time and current_time < next_available_time[task]:
            current_time = next_available_time[task]

        # Update the next available time for the task.
        next_available_time[task] = current_time + cooldown_period + 1

        # Advance the current time.
        current_time += 1

    return current_time

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the array of tasks once, where n is the number of tasks. Inside the loop, for each task, it performs a constant time operation to check its availability and update its next available time using a hashmap. The operations inside the loop (hashmap access and updates) take constant time. Therefore, the overall time complexity is directly proportional to the number of tasks, resulting in O(n).

Space Complexity

O(N) – The solution uses a hash map (or dictionary) to keep track of the next available time for each task. In the worst case, each of the N tasks is unique, meaning the hash map could store up to N entries, each mapping a task to its next available time. Therefore, the auxiliary space required scales linearly with the number of tasks, N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty tasks array	Return 0 since there are no tasks to schedule.
Null tasks array	Throw an IllegalArgumentException or return 0 after checking for null input.
Space is zero	The tasks can be executed consecutively without any cooldown period, return the length of the tasks array.
Tasks array with only one element	Return 1, as only one unit of time is needed to execute a single task.
Tasks array with all identical elements and a large space value	The execution time will be (n-1) * (space + 1) + 1 where n is the number of tasks.
Large tasks array with large space value that causes integer overflow when calculating time	Use long data type for time and potentially space+1 calculation to prevent integer overflow.
Maximum size tasks array	Ensure that the solution's time and space complexity are optimized to handle the maximum array size within the given time and memory constraints, avoiding timeouts or out-of-memory errors.
Space is a large value	Handle the situation when space value is very large, using a HashMap to efficiently store the next available time for each task type.

Empty tasks array

How to Handle:

Return 0 since there are no tasks to schedule.

Null tasks array

How to Handle:

Throw an IllegalArgumentException or return 0 after checking for null input.

Space is zero

How to Handle:

The tasks can be executed consecutively without any cooldown period, return the length of the tasks array.

Tasks array with only one element

How to Handle:

Return 1, as only one unit of time is needed to execute a single task.

Tasks array with all identical elements and a large space value

How to Handle:

The execution time will be (n-1) * (space + 1) + 1 where n is the number of tasks.

Large tasks array with large space value that causes integer overflow when calculating time

How to Handle:

Use long data type for time and potentially space+1 calculation to prevent integer overflow.

Maximum size tasks array

How to Handle:

Ensure that the solution's time and space complexity are optimized to handle the maximum array size within the given time and memory constraints, avoiding timeouts or out-of-memory errors.

Space is a large value

How to Handle:

Handle the situation when space value is very large, using a HashMap to efficiently store the next available time for each task type.