Task Scheduler

Q: What is the time complexity of Task Scheduler?

Counting the letters takes O(m) for m tasks, and the formula then reads 26 counts, so the solution is O(m) time and O(1) extra memory. The max-heap simulation pops once per task, O(m log k) with k ≤ 26 letters.

Q: When does Task Scheduler need no idle time?

When m ≥ (top-1) × (n+1) + atTop , the tasks fill every open slot and stretch the frames instead of leaving gaps, so the answer is m . Example 2, "ABCABD" with n = 1 , is such a case.

MediumGreedy Heap Hashing

+10

You get a string tasks of uppercase letters, one letter per task, and an integer n. A processor runs one task per unit of time, in any order you choose, or stays idle for a unit.

Two runs of the same letter need at least n units between them: a letter that runs at unit t can run again at unit t+n+1 at the earliest. Return the least number of units that runs every task.

Function

leastInterval(tasks: string, n: integer) → integer

tasksstring: the tasks, one uppercase letter each
ninteger: the least number of units between two runs of the same letter
Returnsinteger: the least number of units, idle ones included

Constraints

1 ≤ tasks.length ≤ 10⁴
tasks contains only the uppercase letters A to Z.
0 ≤ n ≤ 100

Examples

Input: tasks = "CACBAC"n = 2
Output: 7
Explanation: C runs three times with two units between runs, so its runs alone span 7 units. The order C A B C A, idle, C fills the gaps with A and B and needs one idle unit: 7.

Input: tasks = "ABCABD"n = 1
Output: 6
Explanation: A and B each run twice with one unit between runs. The order A B C A B D keeps them apart without any idle unit, so the answer is the number of tasks, 6.

Input: tasks = "ZZZ"n = 3
Output: 9
Explanation: Only Z is there to run, so every gap is idle: Z, three idle units, Z, three idle units, Z. That is 9 units.

Follow-up

Can you also return one schedule of the least length, as a string with a . for each idle unit?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

You choose the order, so the question is how few idle units you need. The most frequent letter decides it: its runs must sit n+1 units apart, and the other tasks fill the gaps between them. Run the most frequent letters first with a max-heap, or count the gaps directly in one formula.

Simulate rounds with a max-heap

Intuition

Cut time into rounds of n+1 units. No letter may run twice in a round, and a letter at some slot of one round may run again at the same slot of the next, exactly n+1 units later. In each round, run the letters with the most copies left. Their remaining runs must stay n+1 apart, so they are the ones that can force idle time at the end; running them first keeps the counts level.

A round that leaves work behind costs n+1 units, its empty slots idle; the last round costs only the tasks it ran. In example 1 the rounds run C A B, then C A and one idle unit, then the last C: 3 + 3 + 1 = 7. Each pop runs one task, so with m tasks and k ≤ 26 letters this is O(m log k).

Algorithm

Count each letter and put the counts above zero in a max-heap.
While the heap is not empty, run a round: pop up to n+1 counts and keep each count minus one that is still above zero.
Push the kept counts back.
Add n+1 to the time if the heap is not empty; otherwise add the number of tasks the round ran.
Return the time.

import heapq
from collections import Counter


def leastInterval(tasks, n):
    # heapq is a min-heap, so store negated counts to pop the largest first.
    heap = [-c for c in Counter(tasks).values()]
    heapq.heapify(heap)
    time = 0
    while heap:
        # One round of n+1 slots: run the most frequent tasks left, each at most once.
        left = []
        ran = 0
        while ran < n + 1 and heap:
            c = -heapq.heappop(heap)
            ran += 1
            if c > 1:
                left.append(c - 1)
        for c in left:
            heapq.heappush(heap, -c)
        # A round lasts n+1 units, idle included; the last one ends with its last task.
        time += n + 1 if heap else ran
    return time

Count the frames of the most frequent letter

Intuition

Let top be the highest count, held by letter X. Lay out X with n open slots after each run but the last: top-1 frames of n+1 units, then X's last run. A letter with fewer than top copies fits in the open slots, one copy per frame, so its copies stay at least n+1 apart. Each other letter with top copies adds one unit at the end. With atTop letters at the highest count, that is (top-1) × (n+1) + atTop units.

No schedule is shorter: cut the first (top-1) × (n+1) units into top-1 windows of n+1. Each top letter runs at most once per window, so all atTop of them still have a run left after the windows. With more tasks than open slots, let some frames grow past n+1. A longer frame only widens the gaps, so nothing is idle and the answer is m. The answer is the larger of the two.

Algorithm

Count each of the 26 letters.
Find top, the highest count, and atTop, how many letters have it.
Compute frames = (top-1) × (n+1) + atTop.
Return the larger of frames and the number of tasks.

def leastInterval(tasks, n):
    counts = [0] * 26
    for ch in tasks:
        counts[ord(ch) - ord("A")] += 1
    top = max(counts)
    at_top = counts.count(top)  # tasks that share the highest count
    # top-1 full frames of n+1 units, then one last slot per task at the top count.
    frames = (top - 1) * (n + 1) + at_top
    # With more tasks than frame slots, no idle unit is needed at all.
    return max(frames, len(tasks))

Pitfalls and edge cases

Forgetting the letters tied at the top. In "MMNNPP" with n = 5 all three letters have count 2, so the answer is (2-1) × 6 + 3 = 9, not 7.
Forgetting the larger-of step. In example 2 the frames give (2-1) × 2 + 2 = 4, but six tasks need six units.
Charging the last round a full n+1 units. Nothing waits after the last task: example 3 would give 12 instead of 9.
Pushing a count back inside the round. The same letter can then be popped again in that round and run twice too close together.

Frequently asked questions3

What is the time complexity of Task Scheduler?

Counting the letters takes O(m) for m tasks, and the formula then reads 26 counts, so the solution is O(m) time and O(1) extra memory. The max-heap simulation pops once per task, O(m log k) with k ≤ 26 letters.

When does Task Scheduler need no idle time?

When m ≥ (top-1) × (n+1) + atTop, the tasks fill every open slot and stretch the frames instead of leaving gaps, so the answer is m. Example 2, "ABCABD" with n = 1, is such a case.

Does the order of the input string matter?

No. You choose the order the processor runs the tasks in, so only how many times each letter appears matters. "CACBAC" and "CCCAAB" with n = 2 both need 7 units.

def leastInterval(tasks, n):
    # Write code here

Test #1

Test #2

Test #3

Arguments

tasks = "CACBAC"
n = 2

Expected Output