DSA interview question

Task Scheduler

Medium · Data structures · Topics: heap, greedy, queue, hash map

The problem

A CPU runs tasks labelled by letter, one per time unit. Two runs of the same task must be separated by at least n units, during which the CPU can run other tasks or sit idle. What's the minimum total time to finish all tasks? The most frequent task dictates the shape. With frequency maxFreq, it needs maxFreq − 1 full cooldown frames of length n + 1, plus a final partial frame holding every task that shares that maximum frequency. If there are enough other tasks to fill every gap, there's no idle time at all and the answer is simply the number of tasks.

Example: tasks A A A B B B, n = 2 → 8 (A B idle A B idle A B).

Function signature

int leastInterval(const vector<char>& tasks, int n);  // tasks are 'A'..'Z'

Test cases

Input `(tasks, n)`	Output	Explanation
`(A A A B B B, 2)`	`8`	A B _ A B _ A B
`(A C A B D B, 1)`	`6`	No idle needed
`(A A A B B B, 3)`	`10`	A B _ _ A B _ _ A B
`(A×6, B, C, D, E, F, G, 2)`	`16`	A is the bottleneck: (6 − 1) · 3 + 1
`(A, 5)`	`1`

(Confirm: each task takes one unit; the order is free; idle units are allowed; n ≥ 0.)

How interviewers phrase it

"Given a characters array tasks and a cooling interval n, return the least number of intervals the CPU needs to finish all tasks" (LeetCode 621).

Clarifying questions to ask

Can tasks be reordered freely? (Yes.)
Does the cooldown apply only to identical tasks? (Yes.)
Do I need the schedule or just its length? (Just the length.)

Follow-ups to expect

"Derive the formula."
"Heap simulation?"
"Why is greedy by highest count right?"
"How would you output the schedule?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview