Leetcode 621. Task Scheduler

Problem Explanation

We are given a list of tasks that need to be done by a CPU. The tasks are represented by different capital letters from A to Z. The CPU can only work on a task for a specific interval, meaning it can finish a task or take a break. However, the same task cannot be executed continuously. There needs to be a cooling interval 'n' between two same tasks.

The goal is to find the least number of intervals it will take for the CPU to finish all the tasks.

Walkthrough

Let us take an example to understand this: tasks = ["A","A","A","B","B","B"], n = 2

Here, 'A' and 'B' are the tasks and 2 is the cooling off period. In this case, the CPU will take the following steps: A -> B -> idle -> A -> B -> idle -> A -> B

In total, there are eight intervals that the CPU takes to finish all tasks, hence the output is 8.

Approach

1. If the cooling time is 0, we can simply return the size of the input task array, as every task can be run instantly without any waiting time.

2. Next, we count the frequency of each task. The task with the maximum frequency will determine the number of idle slots.

3. We calculate the number of slots the most frequent task would occupy without having any other task in between.

4. If there are other tasks with the same maximum frequency, we add them to our slot count.

5. Finally, we return the maximum between our slot count and total tasks as the result. This is because if there are not enough tasks to fill the idle slots, then the number of slots will be more than the total number of tasks.

Python Solution

1
2python
3class Solution:
4    def leastInterval(self, tasks, n):
5        if n == 0:
6            return len(tasks)
7
8        taskCount = [0] * 26
9        for task in tasks:
10            taskCount[ord(task) - ord('A')] += 1
11
12        maxFreq = max(taskCount)
13        slotForMaxFreqTask = (maxFreq - 1) * (n + 1)
14        nMaxFreq = taskCount.count(maxFreq)
15     
16        return max(slotForMaxFreqTask + nMaxFreq, len(tasks))

Java Solution

1
2java
3class Solution {
4    public int leastInterval(char[] tasks, int n) {
5        if (n == 0) 
6            return tasks.length;
7        
8        int[] taskCount = new int[26];
9        for (char task: tasks)
10            taskCount[task - 'A']++;
11
12        Arrays.sort(taskCount);
13
14        int maxFreq = taskCount[25];
15        int slotForMaxFreqTask = (maxFreq - 1) * (n + 1);
16        int nMaxFreq = 0;
17        for(int i = 0; i<26; i++)
18        {
19            if(taskCount[i] == maxFreq)
20                nMaxFreq++;
21        }
22        
23        return Math.max(slotForMaxFreqTask + nMaxFreq, tasks.length);
24    }
25}

JavaScript Solution

1
2js
3var leastInterval = function(tasks, n) {
4    if(n === 0)
5        return tasks.length;
6        
7    const taskCount = new Array(26).fill(0);
8
9    for(let task of tasks)
10        taskCount[task.charCodeAt(0) - 65]++;
11
12    taskCount.sort((a, b) => a - b);
13
14    const maxFreq = taskCount[25];
15    const slotForMaxFreqTask = (maxFreq - 1) * (n + 1);
16    let nMaxFreq = 0;
17    for(let i = 0; i<26; i++)
18    {
19        if(taskCount[i] == maxFreq)
20            nMaxFreq++;
21    }
22    
23    return Math.max(slotForMaxFreqTask + nMaxFreq, tasks.length);
24};

C# Solution

1
2csharp
3public class Solution {
4    public int LeastInterval(char[] tasks, int n) 
5    {
6        if(n == 0) 
7            return tasks.Length;
8        
9        int[] taskCount = new int[26];
10        foreach(char task in tasks) 
11        {
12            taskCount[task - 'A']++;
13        }
14
15        Array.Sort(taskCount);
16        int maxFreq = taskCount[25];
17        int slotForMaxFreqTask = (maxFreq - 1) * (n + 1);
18        int nMaxFreq = 0;
19        for(int i = 0; i<26; i++)
20        {
21            if(taskCount[i] == maxFreq)
22                nMaxFreq++;
23        }
24        
25        return Math.Max(slotForMaxFreqTask + nMaxFreq, tasks.Length); 
26    }
27}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int leastInterval(vector<char>& tasks, int n) {
6        if(n == 0)
7            return tasks.size();
8        
9        vector<int> taskCount(26, 0);
10        for(char task : tasks)
11            taskCount[task - 'A']++;
12
13        sort(taskCount.begin(), taskCount.end());
14        int maxFreq = taskCount[25];
15        int slotForMaxFreqTask = (maxFreq - 1) * (n + 1);
16        int nMaxFreq = 0;
17        for(int i = 0; i<26; i++)
18        {
19            if(taskCount[i] == maxFreq)
20                nMaxFreq++;
21        }
22        
23        return max(slotForMaxFreqTask + nMaxFreq, (int)tasks.size());
24    }
25};

Ruby Solution

1
2ruby
3class Solution
4    def least_interval(tasks, n)
5        return tasks.length if n.zero?
6
7        task_count = Array.new(26, 0)
8        tasks.each do |task|
9            task_count[task.ord - 'A'.ord] += 1
10        end
11
12        max_freq = task_count.max
13        slot_for_max_freq_task = (max_freq - 1) * (n + 1)
14        n_max_freq = task_count.count(max_freq)
15
16        [slot_for_max_freq_task + n_max_freq, tasks.length].max
17    end
18end

PHP Solution

1
2php
3class Solution {
4
5    function leastInterval($tasks, $n) {
6        if($n == 0)
7            return sizeof($tasks);
8        
9        $taskCount = array_fill(0, 26, 0);
10        foreach($tasks as $task)
11            $taskCount[ord($task) - ord('A')]++;
12        
13        sort($taskCount);
14        $maxFreq = $taskCount[25];
15        $slotForMaxFreqTask = ($maxFreq - 1) * ($n + 1);
16        $nMaxFreq = 0;
17        foreach($taskCount as $count)
18        {
19            if($count == $maxFreq)
20                $nMaxFreq++;
21        }
22        
23        return max($slotForMaxFreqTask + $nMaxFreq, sizeof($tasks));
24    }
25} 

Go Solution

1
2go
3func leastInterval(tasks []byte, n int) int {
4    if n == 0 {
5        return len(tasks)
6    }
7    
8    taskCount := make([]int, 26)
9    for _, task := range tasks {
10        taskCount[task - 'A']++
11    }
12    
13    sort.Ints(taskCount)
14    maxFreq := taskCount[25]
15    slotForMaxFreqTask := (maxFreq - 1) * (n + 1)
16    nMaxFreq := 0
17    for _, count := range taskCount {
18        if count == maxFreq {
19            nMaxFreq++
20        }
21    }
22    
23    return max(slotForMaxFreqTask + nMaxFreq, len(tasks))
24}
25
26func max(a, b int) int {
27    if a > b {
28        return a
29    }
30    return b
31}

Swift solution

1
2swift
3class Solution {   
4    func leastInterval(_ tasks: [Character], _ n: Int) -> Int {
5        if n == 0 {
6            return tasks.count
7        }
8        
9        var taskCount = Array(repeating: 0, count: 26)
10        for task in tasks{
11            taskCount[Int(task.asciiValue! - Character("A").asciiValue!)] += 1
12        }
13        
14        var maxFreq = taskCount.max()!
15        var slotForMaxFreqTask = (maxFreq - 1) * (n + 1)
16        var nMaxFreq = taskCount.filter { $0 == maxFreq }.count
17        
18        return max(slotForMaxFreqTask + nMaxFreq, tasks.count)
19    }
20}

These are the solutions to solve this task scheduling problem in diverse programming languages. The same approach is applied across all the solutions. The core idea is to find the tasks with maximum frequency, calculate the required slots and then compare it with the total number of tasks.