Task Scheduler

LeetCode 621 | Difficulty: Medium

Medium

Problem Description

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^4`

- `tasks[i]` is an uppercase English letter.

- `0 <= n <= 100`

Topics: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue), Counting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 144 ms)

Metric	Value
Runtime	144 ms
Memory	41.7 MB
Date	2021-12-21

Solution

public class Solution {
    public int LeastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
    int max = Int32.MinValue;
    
    for (int i = 0; i < tasks.Length; i++)
    {
        freq[tasks[i]-'A']++;
        max = Math.Max(freq[tasks[i]-'A'], max);    
    }
    
    int maxFreqCount = freq.Count(x=>x == max);
    
    int result = (max-1) * (n+1) + maxFreqCount;
    return Math.Max(tasks.Length, result);
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: There are many different solutions for this problem, including a greedy algorithm.

Hint 2: For every cycle, find the most frequent letter that can be placed in this cycle. After placing, decrease the frequency of that letter by one.

Hint 3: Use Priority Queue.