leetExpert
Practice

Task Scheduler

Module 19 · Heaps

Problem

Given an array tasks of uppercase letters (each letter is one unit- time task) and a non-negative integer n, find the minimum number of time units needed to complete all tasks, where the same task type must be separated by at least n units of cooldown (during which you may run a different task, or sit idle if none is available). (LeetCode 621.)

Examples

Example 1

Inputtasks = ["A","A","A","B","B","B"], n = 2Output8

Explanation. one valid schedule: A B idle A B idle A B

Example 2

Inputtasks = ["A","A","A","B","B","B"], n = 0Output6

Explanation. no cooldown needed

Constraints

1 ≤ tasks.length ≤ 10⁴, 0 ≤ n ≤ 100, uppercase letters only (at most 26 distinct task types).

Attempt it first

This is the module's most involved problem because it combines a heap-driven greedy simulation with a real correctness argument, not just a mechanical heap-swap. Before opening anything, think through the greedy instinct directly: at any moment when you must choose which task to run next, which task SHOULD you run, to keep your options as open as possible for the future? And separately: why might a most-frequent-task strategy sometimes force idle slots that a less greedy strategy wouldn't?