← Create New Paste

Task Scheduler (LeetCode 621): The Counting Formula and Why It Works

4 views
You are given a list of CPU tasks labeled with letters and a cooldown n: the same task cannot run again until at least n intervals have passed. Each interval runs one task or sits idle. Return the minimum number of intervals needed to finish every task. Example: tasks = A A A B B B, n = 2. One optimal order is A B idle A B idle A B, which takes 8 intervals. Start with the right intuition The most frequent task controls everything. If A appears 3 times and the cooldown is 2, the A's must be at least 3 slots apart, so you get a skeleton: A _ _ A _ _ A. That is (3 - 1) frames of length (n + 1), plus the final A. Other tasks fill the gaps. If there are not enough other tasks, the gaps become idle time. The formula Let maxCount be the highest frequency, and tied be the number of tasks that share that frequency. Then: answer = max(len(tasks), (maxCount - 1) * (n + 1) + tied) Why the max? When there are many distinct tasks, all gaps fill up and you never idle, so the answer is just the number of tasks. The formula covers both cases in one line. Python from collections import Counter def least_interval(tasks, n): counts = Counter(tasks).values() max_count = max(counts) tied = sum(1 for c in counts if c == max_count) return max(len(tasks), (max_count - 1) * (n + 1) + tied) Time is O(T) to count, space O(1) since there are at most 26 letters. The simulation alternative Some interviewers want to see a greedy simulation, especially as a follow-up ("now return the actual schedule"). Use a max-heap of remaining counts and a queue of tasks that are cooling down with the time they become available. Each tick, pop the most frequent available task, decrement it, and push it into the cooldown queue; move tasks back to the heap when their time arrives. This is O(T log 26) and generalizes to variants like Reorganize String, where n = 1 and you must return a valid arrangement. Details worth saying out loud - Why greedy by highest count? Running the most frequent task first keeps it from bunching up at the end, which is where forced idle time comes from. - Edge case n = 0: the answer is simply len(tasks), and the formula handles it. - Ties matter. With A A A B B B and n = 2, both A and B have count 3, so tied = 2 and the formula gives 2 * 3 + 2 = 8. How to present it Explain the skeleton picture first, then derive the formula from it, then mention the heap version as the general approach. Interviewers appreciate when you test the formula on a case with lots of distinct tasks, such as A B C D E F with n = 2, to show why the max is needed. Calm explanations under time pressure Deriving a formula live is harder than remembering it. If you want support during the real interview, Linkjob AI (https://linkjob.ai) offers real-time help during live job interviews and technical interviews, suggesting hints and structure while you reason through the problem yourself. Practice both the formula and the heap simulation until you can explain each in two minutes.
Created Nov 17, 2026 15:58 Expires Nov 17, 2027 15:58