Task Scheduler
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Given tasks (letters) and a cooldown n, the same task needs at least n slots between two runs. Return the minimum number of time slots to finish all tasks (idle slots allowed).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Count how often each task appears. Which count shapes the schedule?
- Hint 2If the busiest task appears m times, there are m-1 full rows of size n+1, then a last partial row.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A doctor who must rest n minutes before seeing the same patient again. If one patient (A) needs 3 visits, you must see A, then n other things (other patients or just rest), then A again, then n other things, then A. These "rows" of length n+1 are fixed by the busiest patient. Other patients just fill the empty spots in the rows; if there are too few, the doctor rests.
- The obvious way
Simulate each slot with a heap, picking the available task with the most remaining: O(total time x log 26).
- The key insight
Let m be the highest count and ties be the number of tasks having that count. The frame is (m - 1) rows of length (n + 1), plus a last row of size ties: (m - 1) x (n + 1) + ties. If the tasks do not even fit, there is no idle time and the answer is just the number of tasks, so take the bigger of the two.
- The algorithm
- Count each letter.
- m = the highest count; ties = how many letters have it.
- frame = (m - 1) x (n + 1) + ties.
- Answer = max(frame, number of tasks).
Watch it run
Exampletasks = [A, A, A, B, B, B], n = 2
A and B each appear 3 times: m = 3, and 2 letters tie for it.
m = 3, ties = 2
Where people slip
- Take max with the number of tasks: with many different tasks no idle slot is needed.
- Count ties: several tasks sharing the top count all appear in the last row.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
from collections import Counter
def least_interval(tasks, n):
counts = Counter(tasks).values()
most = max(counts) # how often the busiest task runs
ties = sum(1 for count in counts if count == most) # tasks that are just as busy
frame = (most - 1) * (n + 1) + ties
return max(frame, len(tasks)) # no idle time if everything already fitsNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.