Task Scheduler
A CPU runs tasks labelled by letters, one task or one idle slot per unit of time. Two identical tasks must be separated by at least n time units. Return the minimum total time to finish all tasks.
- 1 ≤ tasks.length ≤ 10^4
- tasks[i] is an uppercase letter
- 0 ≤ n ≤ 100
- Always schedule the task with the most remaining instances
- Cooldown means recently used tasks are temporarily unavailable
- Max-heap of counts plus a queue of cooling tasks
When you repeatedly need the minimum or maximum of a changing collection, a heap gives O(log n) insert and extract instead of re-sorting. "Top k" problems keep a heap of size k for O(n log k); a "median of stream" balances a max-heap of the lower half against a min-heap of the upper half.
Count tasks and push the counts into a max-heap. Simulate time in rounds of n + 1 slots: pop up to n + 1 tasks with the highest counts, run each once, and reinsert those with remaining work after the round. Each full round costs n + 1 time unless the heap empties, in which case only the tasks actually run count. Greedily preferring the most frequent task keeps the idle slots minimal.
- A closed-form formula
max(T, (maxCount - 1) · (n + 1) + numberOfTasksWithMaxCount)computes the answer in O(T) without simulation.