{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Task Scheduler – Solution & Complexity

Interview solutions
/
Task Scheduler

Solution Walkthrough

  1. Step 1: Understand the bottleneck

    • The hard part is not ordering every task individually; it is respecting the cooldown for the most frequent letter.
    • If one task appears much more often than the rest, the schedule needs gaps between its copies, and those gaps must be filled by other tasks or by idle slots.

  2. Step 2: Brute-force baseline

    • A direct simulation keeps a max-heap of currently available task counts plus a cooldown queue storing when a task can be used again.
    • That works and is a good interview stepping stone, but it still simulates every interval explicitly, including idle time.

  3. Step 3: Optimal counting insight

    • Let maxFreq be the highest task frequency. Place those copies first as maxFreq - 1 full rows separated by n cooldown slots.
    • If maxCount tasks tie for that same highest frequency, they all occupy the last column of the frame. The minimum required frame length is (maxFreq - 1) * (n + 1) + maxCount.
    • The real answer is the larger of that frame length and the total number of tasks, because abundant filler tasks can eliminate all idle intervals.

  4. Step 4: Final solution (all languages)

    The counting formula runs in linear time over the task list and constant extra space because the alphabet size is fixed.

    def least_interval(tasks: list[str], n: int) -> int:
    counts = [0] * 26
    for task in tasks:
        counts[ord(task) - ord('A')] += 1

    max_freq = max(counts)
    max_count = sum(1 for count in counts if count == max_freq)
    frame = (max_freq - 1) * (n + 1) + max_count
    return max(len(tasks), frame)

  5. Step 5: Common mistakes and follow-ups

    • Forgetting the tie case: if multiple tasks share the same maximum frequency, you need all of them in the last row, not just one.
    • Returning the frame length directly even when many filler tasks exist; the answer can never be smaller than tasks.length.
    • Follow-up: if asked to print a valid schedule, switch to the heap + cooldown simulation and emit each chosen task or an idle marker.

FAQ

See also

Practice Task Scheduler online (run code in the browser)Find Median from Data Stream solution (hard)K Closest Points to Origin solution (medium)Kth Largest Element in an Array solution (medium)Merge K Sorted Lists solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?