76. Task Scheduler with Cooldown
Schedule all task occurrences so that equal task labels are separated by the required cooldown. Different labels may fill the gaps, and idle slots may be inserted when necessary.
Task order can be rearranged. You need the minimum elapsed schedule length, not a particular schedule or just the count of task occurrences.
Example 1
Input
tasks=AAABBB, cooldown=2
Output
8
Explanation: One optimum is A,B,idle,A,B,idle,A,B. Equal labels start three slots apart.
Example 2
Input
tasks=ABCABC, cooldown=0
Output
6
Explanation: All occurrences fit without idle slots; workload count dominates any frame bound.
Example 3
Input
tasks=AAA, cooldown=MAX
Output
4,294,967,297
Explanation: Two huge cooldown gaps are represented by long arithmetic and compressed idle blocks, not billions of loop iterations.
Example 4
Input
tasks=[], cooldown=0
Output
0
Explanation: No maximum-frequency frame is needed.
Constraints
0 <= tasks.length <= 1050 <= cooldown <= 231 - 1- tasks contains only uppercase English letters A–Z.
Hints
Hint 1
What independent lower bounds come from total work and the most frequent labels?
Hint 2
Count all labels tied at the largest frequency, not only one anchor.
Hint 3
Compute max(n,(f−1)*(c+1)+t) in long; use eligibility-aware simulation only when constructing a witness.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Tied dominant tasks require forced idle
"AAABBB"
2
8