Coding

Task Scheduler

Asked at

Google

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given a list of tasks represented by uppercase English letters ('A' to 'Z'), and an integer n representing a cooldown interval between two same tasks.

Each task takes exactly 1 CPU interval to complete. Tasks can be executed in any order, but identical tasks must be separated by at least n intervals, during which the CPU may remain idle or execute other tasks.

Return the minimum number of **CPU **intervals required to complete all the tasks.

Input: tasks = ["A","A","A","B","B","B"], n = 2 **Output: **8 Explanation:

One valid execution order is:
A -> B -> idle -> A -> B -> idle -> A -> B
Total intervals = 8

Input: tasks = ["A","C","A","B","D","B"], n = 1 Output: 6 Explanation:

A possible execution:
A -> B -> C -> D -> A -> B
No idle interval is needed as cooldown = 1.

Input: tasks = ["A","A","A","B","B","B"], n = 3

1 <= tasks.length <= 104
tasks[i] is an uppercase English letter from 'A' to 'Z'
0 <= n <= 100

cpp

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        // Your code goes here
    }
};

java

class Solution {
    public int leastInterval(char[] tasks, int n) {
        // Your code goes here
    }
}

python

class Solution:
    def leastInterval(self, tasks, n):
        # Your code goes here

javascript

class Solution {
    leastInterval(tasks, n) {
        // Your code goes here
    }
}

csharp

class Solution {
    public int LeastInterval(char[] tasks, int n) {
        // Your code goes here
    }
}

func leastInterval(tasks []byte, n int) int {
    // Your code goes here
}

Stuck? Show a way to structure it+

01Count task frequencies and find the maximum count.
02Compute the required cooldown frame around max-frequency tasks.
03Account for how many task types share that maximum.
04Take the maximum of frame length and task count.

Reference answer

Let maxFreq be the largest frequency and maxCount the number of task types reaching it. Arrange the max-frequency tasks in maxFreq - 1 frames of size n + 1, then append the maxCount final tasks. The minimum schedule length is max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount). Other tasks fill idle slots when possible. Counting is O(n) with a fixed 26-letter array. A simulation heap is valid but unnecessary for this version. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

How would you output an actual schedule?
Tests: heap simulation
What changes with different task durations?
Tests: general scheduling

Hiring now

Google has 52 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Small Business Field Sales Representative
Denver, Colorado
Senior Technical Program Manager, Special Projects
Denver, Colorado; Lakewood, Colorado, United States
OSP Engineering Lead, Technical Operations
Denver, Colorado

Or practice this question first

Next question