Task Scheduler Heap

Minimize CPU idle time by scheduling tasks with a cooldown using a max-heap.

heap queue greedy scheduling

You are given a list of tasks, each represented by a single uppercase letter (A-Z). The same task must be separated by at least `n` intervals (cooldown), where each interval can either be executing a task or being idle. You can execute at most one task per interval. You may arrange the tasks in any order. Write a function `least_intervals(tasks, n)` that returns the minimum number of intervals required to finish all tasks.

**Function signature:** `def least_intervals(tasks: list[str], n: int) -> int:`

**Input:**
- `tasks`: list of strings, each string is a single uppercase letter.
- `n`: integer >= 0, the cooldown period.

**Output:**
- Integer: minimum total intervals needed.

**Note:** You do not need to output the actual schedule, only the count.

Constraints

- 1 <= len(tasks) <= 10^4
- 0 <= n <= 100
- tasks[i] is a single uppercase English letter.
- Solution must run in O(N log N) or better, where N is the number of tasks.

Example

>>> least_intervals(['A','A','A','B','B','B'], 2)
8
>>> least_intervals(['A','A','A','B','B','C'], 1)
6
>>> least_intervals(['A','A','A'], 2)
7
>>> least_intervals(['A','B','C'], 1)
3

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a max-heap (store negative counts) to always pick the most frequent available task.

Simulate one cycle of (n+1) intervals: each interval either picks a task with remaining count > 0 or idles.

After each cycle, decrement counts of executed tasks and push them back if they still remain.

The total intervals is the sum of all cycles processed until the heap is empty.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.