LietCode
Task Scheduler (Medium)

Task Scheduler (Medium)

Abhi's photo
Abhi
·

4 min read

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.

1) Explain the problem

You are given an array of CPU tasks represented by letters A to Z and an integer n representing the cooling time between identical tasks. Each task takes one interval to complete. You need to find the minimum number of intervals required to complete all the tasks such that no two identical tasks are within n intervals of each other.

2) Short easy to remember solution/approach

Use a greedy approach with a priority queue (max heap) to schedule tasks efficiently while respecting the cooling time constraint. Keep track of the tasks and their frequencies, and use a queue to manage the cooling periods.

3) Solution in JavaScript with code commenting

function leastInterval(tasks, n) {
    // Step 1: Count the frequency of each task
    const taskCounts = new Array(26).fill(0);
    for (const task of tasks) {
        taskCounts[task.charCodeAt(0) - 'A'.charCodeAt(0)]++;
    }

    // Step 2: Create a max heap for the task frequencies
    const maxHeap = [];
    for (const count of taskCounts) {
        if (count > 0) {
            maxHeap.push(count);
        }
    }
    maxHeap.sort((a, b) => b - a); // Max heapify

    // Step 3: Initialize the intervals counter
    let intervals = 0;

    // Step 4: Process tasks
    while (maxHeap.length > 0) {
        const temp = [];
        let i = 0;
        // Fill the cooling period of size n + 1
        while (i <= n) {
            if (maxHeap.length > 0) {
                if (maxHeap[0] > 1) {
                    temp.push(maxHeap[0] - 1);
                }
                maxHeap.shift(); // Remove the max task
            }
            intervals++;
            if (maxHeap.length === 0 && temp.length === 0) break;
            i++;
        }
        for (const t of temp) {
            maxHeap.push(t);
        }
        maxHeap.sort((a, b) => b - a); // Reheapify
    }

    return intervals;
}

4) Explanation of the solution in an easy-to-understand way

Imagine you have a bunch of tasks (like A, B, C) and you need to complete them on your computer. However, if you do the same task too soon after doing it once, your computer needs some cooling time (like a break). So, you need to schedule these tasks in such a way that no two same tasks are too close to each other. The idea is to always pick the task that you haven't done for the longest time and is the most frequent, and keep track of the breaks your computer needs.

5) Code explanation in pointers

  1. Count Frequencies: Count how many times each task appears.

  2. Max Heap Creation: Use a max heap to keep track of the most frequent tasks.

  3. Initialize Intervals: Start counting the intervals needed.

  4. Process Tasks: Use a loop to process the tasks, ensuring that no two same tasks are within n intervals by using a temporary list to manage the tasks in the cooling period.

  5. Heap Reheapify: After processing the tasks in the cooling period, reheapify the heap.

6) Complexities

  • Time Complexity: O(N log N), where N is the number of tasks. This is due to the sorting of the heap after every interval.

  • Space Complexity: O(N), where N is the number of tasks, for the heap and the temporary storage during processing.

heap