Task Scheduler

MediumArray Hash Table Greedy Heap

An integration job has to send a batch of API requests, tasks, where each request is labelled with the endpoint it calls: an uppercase letter from A to Z. Sending one request takes exactly one time unit, and in each unit the client either sends one request or waits idle.

The API enforces a rate limit: between two requests to the same endpoint there must be at least n other time units, filled with other requests or with idling. The requests may be sent in any order.

Return the minimum number of time units needed to send every request.

Example 1

Input: tasks = ["P","P","P","Q","R"], n = 2
Output: 7

Explanation: One best order is P Q R P idle idle P. The three P requests need two gaps of two units each, and Q and R can only fill the first gap.

Example 2

Input: tasks = ["X","Y","X","Y"], n = 1
Output: 4

Explanation: X Y X Y already keeps repeated endpoints one unit apart, so no idling is needed.

Example 3

Input: tasks = ["M","M","M","N"], n = 3
Output: 9

Explanation: M N idle idle M idle idle idle M: the three M requests decide the length.

Constraints

tasks holds between 1 and 10^4 requests.
Every request label is an uppercase English letter.
n is between 0 and 100.

💡 Hint 1

Only the counts matter, not the order of the input. Which task constrains the schedule the most?

💡 Hint 2

Lay out the most frequent task (count f) first: it creates f - 1 frames of length n + 1, followed by a final partial frame.

💡 Hint 3

The final frame holds every task tied for the top count. If there are more tasks than frame slots, no idling is needed at all and the answer is simply tasks.length.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Count each label. Let f be the highest count and m the number of labels that reach it. Schedule the most frequent task first: its f copies need f - 1 frames of n + 1 units each (one copy plus n cooling slots), then a last frame holding the m tasks tied at the top, for (f - 1) · (n + 1) + m units. Every other task fits into the cooling slots, because each has fewer than f copies and so never collides with itself. If the slots overflow, the schedule simply stretches with no idling at all, and its length is tasks.length. The answer is the larger of the two. (Simulating with a max-heap of counts and a cooldown queue gives the same result in O(n log 26).)

Time O(n)Space O(1) (26 counters)

function leastInterval(tasks, n) {
  const count = new Array(26).fill(0);
  for (const t of tasks) count[t.charCodeAt(0) - 65]++;
  const maxFreq = Math.max(...count);
  const tiedAtMax = count.filter((c) => c === maxFreq).length;
  return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + tiedAtMax);
}

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        int maxFreq = 0;
        for (char t : tasks) maxFreq = Math.max(maxFreq, ++count[t - 'A']);
        int tiedAtMax = 0;
        for (int c : count) if (c == maxFreq) tiedAtMax++;
        return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + tiedAtMax);
    }
}

/**
 * @param {string[]} tasks one-character strings "A".."Z"
 * @param {number} n
 * @return {number}
 */
function leastInterval(tasks, n) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit