LeetCode 621: Task Scheduler Solution

Master LeetCode problem 621 (Task Scheduler), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

621. Task Scheduler

Medium

Array Hash Table Greedy Sorting Heap (Priority Queue)Counting

Problem Explanation

Explanation:

To solve this problem, we need to first identify the most frequent task and calculate how many intervals are needed to complete all instances of this task. Then, we need to place the remaining tasks in such a way that the cooldown period constraint is satisfied. The minimum number of intervals required will be the maximum of two cases: 1) the total number of intervals needed to complete all tasks, and 2) the length of the input tasks array.

Algorithm:

Create a frequency map to count the occurrences of each task.
Find the task with the maximum frequency.
Calculate the minimum number of intervals needed to complete all instances of the most frequent task.
Calculate the idle slots needed to satisfy the cooldown period constraint.
Return the maximum of the total number of intervals or the length of the tasks array.

Time Complexity: O(n) Space Complexity: O(1) :

Solution Code

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 maxFreq = freq[25] - 1;
        int idleSlots = maxFreq * n;
        
        for (int i = 24; i >= 0 && freq[i] > 0; i--) {
            idleSlots -= Math.min(freq[i], maxFreq);
        }
        
        return idleSlots > 0 ? idleSlots + tasks.length : tasks.length;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 621 (Task Scheduler)?

This page provides optimized solutions for LeetCode problem 621 (Task Scheduler) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 621 (Task Scheduler)?

The time complexity for LeetCode 621 (Task Scheduler) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 621 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 621 in Java, C++, or Python.

Back to LeetCode Solutions