Task Scheduler LeetCode

Many LeetCode problems involve scheduling, focusing on optimizing resource use and minimizing completion time, whether it's for job scheduling, CPU scheduling, or project durations. The goal is to efficiently utilize resources to enhance productivity and reduce costs across various applications. The Task Scheduler problem introduces an added complexity: a cooling period between identical tasks. This constraint requires careful planning to respect cooldown periods while still optimizing resource use and minimizing overall completion time, reflecting the real-world challenges faced in task management systems.

Problem statement

Given a character array tasks, where each character represents a unique task and a positive integer n that represents the cooling period between any two identical tasks, find the minimum number of time units the CPU will need to complete all the given tasks. Each task requires one unit to perform, and the CPU must wait for at least n units of time before it can repeat the same task. During the cooling period, the CPU can perform other tasks or remain idle.

Constraints:

$1 \leq$ tasks.length $\leq 1000$
$0 \leq$ n $\leq 100$
tasks consists of uppercase English letters

Let’s take a look at a few examples to get a better understanding of the problem statement:

Solution

An optimal strategy is to schedule the most frequent task first, then the second most frequent task, and so on. This is because once we’ve scheduled the most frequent task, we can get an estimate of the maximum idle time. Therefore, we keep track of the frequencies of all tasks using a hash map, frequencies. Let’s say we have tasks = $[A,B,C,A,B,A]$ and n = 2, then frequencies = $\{ A: 3, ~B: 2, ~C:1\}$ . Then, we sort these frequencies so that we can use them later to schedule the tasks in descending order. The most frequent task, i.e., $A$ can be scheduled as $A ~\_~\_~A~\_~\_~A$ . Here, we have four idle slots, which can be calculated as:

$Idle~time = (Max~frequency - 1) \times n$

Next, we utilize these idle slots to schedule the remaining tasks. The next most frequent task is $B$ , which can be scheduled as: $A ~B~\_~A~B~\_~A$ . Now, we’re left with only two idle slots. In general, for every scheduled task, other than the most frequent, the idle slots can be calculated as:

$Idle~time = Idle~time - Current~frequency$

Finally, we can schedule task $C$ in any of the two idle slots. For example: $A ~B~C~A~B~\_~A$ . After scheduling task $C$ , all tasks have been scheduled. Therefore, the CPU requires $7$ units of time to perform tasks = $[A,B,C,A,B,A]$ with n = 2.

The formula above works fine as long as $Current~frequency < Max~frequency$ . In other words, if we have more than one task having the maximum frequency, the equation above doesn’t hold. Therefore, we consider the maximum frequency at every step, and the formula is modified as:

$Idle~time = Idle~time - min(Max~frequency - 1,~ Current~frequency)$

For example, tasks = $[A,A,B,B]$ and n = $2$ . After scheduling task $A$ as $A~\_~\_~A$ , the remaining idle slots become $2$ . Now, if we schedule task $B$ as $A~B~B~A$ , we break the cooling period rule. Therefore, we need to schedule it as $A~B~\_~A~B$ . Using the equation above, the idle time comes out to be $1$ because $Idle~time = 2 - min(2 - 1,~ 2) = 1$ .

In general, the total time required by the CPU can be calculated as:

$Total~time = Number~of~tasks + Idle~time$

Let’s look at the following illustration to get a better understanding of the solution:

def least_time(tasks, n):
    # initialize a dictionary to store the frequencies of the tasks
    frequencies = {}
    # store the frequency of each task
    for t in tasks:
        frequencies[t] = frequencies.get(t,0) + 1
    
    # sort the frequencies
    frequencies = dict(sorted(frequencies.items(), key=lambda x:x[1]))
    # store the max frequency
    max_freq = frequencies.popitem()[1]
    # compute the maximum possible idle time
    idle_time = (max_freq - 1) * n
    # iterate over the freqencies array and update the idle time
    while frequencies and idle_time > 0:
        idle_time -= min(max_freq - 1, frequencies.popitem()[1])
    idle_time = max(0, idle_time)
    # return the total time, which is the sum of the busy time and idle time
    return len(tasks) + idle_time
# driver code
def main():
    all_tasks = [['A', 'A', 'B', 'B'],
                 ['A', 'A', 'A', 'B', 'B', 'C', 'C'],
                 ['S', 'I', 'V', 'U', 'W', 'D', 'U', 'X'],
                 ['M', 'A', 'B', 'M', 'A', 'A', 'Y', 'B', 'M'],
                 ['A', 'K', 'X', 'M', 'W', 'D', 'X', 'B', 'D', 'C', 'O', 'Z', 'D', 'E', 'Q']]
    all_ns = [2, 1, 0, 3, 3]
    for i in range(len(all_tasks)):
        print(i+1, '.', '\tTasks: ', all_tasks[i], sep='')
        print('\tn: ', all_ns[i], sep='')
        min_time = least_time(all_tasks[i], all_ns[i])
        print('\tMinimum time required to execute the tasks: ', min_time)
        print('-' * 100)
if __name__ == '__main__':
        main()

Task Scheduler

Complexity analysis

Let’s analyze the time and space complexity of our solution.

Time complexity

The time complexity of counting the frequencies of tasks is $O(n)$ , where $n$ is the total number of tasks. Sorting the frequencies takes constant time $O(1)$ due to the fixed size (26 for the 26 letters of the alphabet). The proceeding steps also take constant time. Consequently, the overall time complexity of the solution is $O(n)$ .

Space complexity

The space complexity is $O(1)$ because it requires constant space to store task frequencies.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments