Task Scheduler

Medium

Roblox

0 views

Topics:

ArraysGreedy Algorithms

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3^rd interval, neither A nor B can be done, so you idle. By the 4^th interval, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = ["A","C","A","B","D","B"], n = 1

Output: 6

Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = ["A","A","A", "B","B","B"], n = 3

Output: 10

Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:

1 <= tasks.length <= 10⁴
tasks[i] is an uppercase English letter.
0 <= n <= 100

Task Scheduler

Medium

Roblox

0 views

Topics:

ArraysGreedy Algorithms

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3^rd interval, neither A nor B can be done, so you idle. By the 4^th interval, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = ["A","C","A","B","D","B"], n = 1

Output: 6

Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = ["A","A","A", "B","B","B"], n = 3

Output: 10

Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:

1 <= tasks.length <= 10⁴
tasks[i] is an uppercase English letter.
0 <= n <= 100

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 is the maximum possible value of `n` and the length of the character array?
Can the character array be empty or contain null values?
Are the tasks case-sensitive? For example, is 'A' different from 'a'?
If n is zero, does that mean I can execute tasks of the same type back-to-back?
If the number of tasks of the most frequent type is such that the 'idle slots' are not enough to fit the other tasks, should I return the total number of tasks?

Brute Force Solution

Approach

The brute force approach to the task scheduler problem involves trying every single possible order of tasks. We essentially simulate running the tasks in each possible order and calculating the total time it takes. This ensures we eventually find the fastest arrangement, but it's also very inefficient.

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

Start by considering all possible sequences in which we can perform the tasks.
For each possible sequence, simulate the execution of the tasks one by one.
Keep track of the time elapsed as we execute each task, considering the cooldown period if needed.
If a cooldown period is necessary, simply skip time slots until the cooldown is complete.
Once we have simulated the entire sequence of tasks, record the total time taken.
Repeat steps 2-5 for all other possible task sequences.
Finally, compare the total time taken for all the sequences and pick the sequence that results in the shortest time.

Code Implementation

import itertools

def task_scheduler_brute_force(tasks, cooldown_period):
    shortest_time = float('inf')

    # Generate all possible task permutations
    for task_permutation in itertools.permutations(tasks):
        current_time = 0
        last_executed = {}

        for task in task_permutation:
            # Check if cooldown is needed
            if task in last_executed and \
               current_time - last_executed[task] <= cooldown_period:
                current_time = last_executed[task] + cooldown_period + 1

            last_executed[task] = current_time
            current_time += 1

        # Update shortest time if needed
        shortest_time = min(shortest_time, current_time)

    return shortest_time

Big(O) Analysis

Time Complexity

O(n!) – The brute force approach considers all possible orderings of the n tasks. Generating all permutations of n tasks takes n! (n factorial) time. For each of these n! permutations, we simulate the task execution, which takes O(n) time where n is the number of tasks. Therefore, the overall time complexity is O(n! * n), which simplifies to O(n!) since the factorial term dominates. Thus, the time complexity is driven by the need to explore every possible task sequence.

Space Complexity

O(N!) – The brute force approach explores all possible task sequences, which requires generating permutations of the input tasks. The number of possible permutations for N tasks is N! While the algorithm doesn't explicitly store all permutations simultaneously, the recursive calls involved in generating permutations create a call stack that can grow to a depth related to N. This call stack stores intermediate permutations, resulting in auxiliary space usage proportional to the number of active calls, ultimately leading to a space complexity of O(N!).

Optimal Solution

Approach

The most efficient strategy focuses on the most frequent task and arranges the others around it. We calculate the minimum time required based on how often the most frequent task needs to be spaced out, then fit in the remaining tasks where possible. This avoids simulating every possible task arrangement.

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

Figure out which task appears most often.
Determine the idle time needed based on the frequency of the most frequent task and the cool-down period.
Try to fill in the idle slots with other available tasks.
If there are more tasks than idle slots, there's no idle time, so just calculate the total number of tasks.
If there's still idle time after adding other tasks, add that remaining idle time to the total number of tasks to find the minimum time needed.

Code Implementation

def least_interval(tasks, cool_down_interval):
    task_counts = {}
    for task in tasks:
        task_counts[task] = task_counts.get(task, 0) + 1

    max_frequency = 0
    for task in task_counts:
        max_frequency = max(max_frequency, task_counts[task])

    # Calculate idle slots needed for the most frequent task.
    idle_slots = (max_frequency - 1) * (cool_down_interval + 1)

    for task in task_counts:
        if task_counts[task] == max_frequency:
            idle_slots -= 1

    idle_slots = max(0, idle_slots)

    # If idle_slots is positive, add it to the total tasks.
    return len(tasks) + idle_slots

Big(O) Analysis

Time Complexity

O(n) – The dominant operation is counting the frequency of each task which involves iterating through the input list of tasks of size n. Finding the maximum frequency also takes O(n) time in the worst case where n is the number of unique task types if we use a data structure like a dictionary to store the counts. All other calculations, such as determining idle time and filling slots, involve constant time operations or iterations bounded by the number of unique task types, which is at most n. Therefore, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm primarily focuses on calculating the minimum time based on the frequency of tasks, without using auxiliary data structures that scale with the input size (number of tasks). While counting task frequencies might implicitly use a fixed-size data structure (like a hash map or array) dependent on the character set of tasks, this is considered constant space as it is independent of the number of tasks N. Therefore, the space complexity is dominated by a few integer variables, resulting in O(1) auxiliary space.

Edge Cases

Case	How to Handle
Null or empty task array	Return 0 since there are no tasks to schedule.
n is 0, meaning no cooldown is required	Return the length of the tasks array directly.
Array contains only one type of task	The result will be (count - 1) * (n + 1) + count.
n is a very large number compared to task array size	The number of idle slots calculation needs to ensure it does not result in negative values or overflow.
Tasks are already optimally distributed (e.g., ['A', 'B', 'C', 'A', 'B', 'C'] with n=2)	The algorithm should handle cases without additional idle time needed.
Integer overflow when calculating the total time	Use long data types for intermediate calculations where necessary.
Very large input array size for tasks	The solution's space complexity (frequency map) should be efficient enough for a large number of tasks.
Tasks are mostly unique, but still requires cooldowns	Ensure even relatively low-frequency tasks are still processed with the proper cooldown time.