Heap / Priority Queue · 129Medium
Task Scheduler
Given an array of CPU tasks labelled A-Z and a cooldown n, identical tasks must be separated by at least n intervals. Each task takes one interval, and the CPU may idle. Return the minimum number of intervals needed to finish all tasks.
Constraints
- 1 <= tasks.length <= 10^4
- tasks[i] is an uppercase English letter.
- 0 <= n <= 100
Examples
leastInterval(["A","A","A","B","B","B"], 2) -> 8 // A B idle A B idle A B leastInterval(["A","A","A","B","B","B"], 0) -> 6 // no cooldown leastInterval(["A","A","A","A"], 2) -> 10 leastInterval(["A"], 0) -> 1 // a single task leastInterval(["A","B","C","D"], 2) -> 4 // all distinct, never idle leastInterval(["A","A","B","B"], 2) -> 5 // a tie for most frequent shrinks idling
Edge cases
- n = 0 means the answer is simply the task count.
- The answer is never below the total number of tasks.
Show the target complexity (spoiler)
- Naive
- Simulating interval by interval with a scan for the best available task is O(total *
- Target
- O(n) time — either a max-heap with a cooldown queue, or the closed form: max(tasks.length, (maxFreq - 1) * (n + 1) + countOfMaxFreq).
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/13-heap-priority-queue/129-task-scheduler.js ./practice c 129