Task Scheduler
Medium Greedy counting
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
CPU tasks are letters; the same letter needs at least n intervals between runs. Each interval runs one task or idles. Return the minimum number of intervals.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: least time to run tasks when the same task needs n gaps between runs.
Why this works: the most frequent task sets a frame: (max - 1) blocks of size n + 1, plus one slot for each task tied at max. If there are more tasks than slots, no idling is needed.
Example: A A A B B B, n = 2
(3 - 1) × 3 + 2 = 8A B _ A B _ A B
✦Hints open one at a time
↗Approach
Answer = max(tasks.length, (maxCount − 1) × (n + 1) + numberOfTasksWithMaxCount). (A max-heap simulation also works and is good practice.)
</>Solution (Java)
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] count = new int[26];
int max = 0;
for (char t : tasks) max = Math.max(max, ++count[t - 'A']);
int maxCount = 0;
for (int c : count) if (c == max) maxCount++;
int frame = (max - 1) * (n + 1) + maxCount; // most frequent task sets the frame
return Math.max(tasks.length, frame);
}
}!Common mistake
Forgetting the max with tasks.length, which gives too small an answer when there's no idle time.
- Time: O(m), m = number of tasks.
- Space: O(26).