Last updated on February 20th, 2025 at 09:04 am
Here, we see a Task Scheduler LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Greedy, Queue
Companies
Level of Question
Medium
Task Scheduler LeetCode Solution
Table of Contents
1. Problem Statement
You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there’s a constraint: identical tasks must be separated by at least n intervals due to cooling time.
Return the minimum number of 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 cycles before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th cycle, 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.
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Greedy Algorithm with Frequency Counting”. This pattern involves counting the frequency of tasks, sorting them, and greedily calculating the minimum idle time required to schedule tasks with a cooldown period (n).
3. Code Implementation in Different Languages
3.1 Task Scheduler C++
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
int freq[26] = {0};
for(char task : tasks){
freq[task - 'A']++;
}
sort(begin(freq) , end(freq));
int chunk = freq[25] - 1;
int idel = chunk * n;
for(int i=24; i>=0; i--){
idel -= min(chunk,freq[i]);
}
return idel < 0 ? tasks.size() : tasks.size() + idel;
}
};
3.2 Task Scheduler Java
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char task : tasks) {
freq[task - 'A']++;
}
Arrays.sort(freq);
int chunk = freq[25] - 1;
int idle = chunk * n;
for (int i = 24; i >= 0; i--) {
idle -= Math.min(chunk, freq[i]);
}
return idle < 0 ? tasks.length : tasks.length + idle;
}
}
3.3 Task Scheduler JavaScript
var leastInterval = function(tasks, n) {
let freq = Array(26).fill(0);
for (let task of tasks) {
freq[task.charCodeAt(0) - 'A'.charCodeAt(0)]++;
}
freq.sort((a, b) => b - a);
let chunk = freq[0] - 1;
let idle = chunk * n;
for (let i = 1; i < 26; i++) {
idle -= Math.min(chunk, freq[i]);
}
return idle < 0 ? tasks.length : tasks.length + idle;
};
3.4 Task Scheduler Python
class Solution(object):
def leastInterval(self, tasks, n):
freq = [0] * 26
for task in tasks:
freq[ord(task) - ord('A')] += 1
freq.sort()
chunk = freq[25] - 1
idle = chunk * n
for i in range(24, -1, -1):
idle -= min(chunk, freq[i])
return len(tasks) + idle if idle >= 0 else len(tasks)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(1) |
| Java | O(n) | O(1) |
| JavaScript | O(n) | O(1) |
| Python | O(n) | O(1) |
where, n is the number of tasks.
- The code efficiently calculates the minimum time required to schedule tasks with a cooldown period using a greedy approach.
- Sorting a fixed-size array (26 elements) is effectively constant time.
- The algorithm is highly optimized for the given problem constraints.