def leastInterval(self, tasks, N): task_counts = collections.Counter(tasks).values() M = max(task_counts) Mct = task_counts.count(M) return max(len(tasks), (M - 1) * (N + 1) + Mct)
Let's say the most frequent tasks occur
M times, and there are
Mct of them.
N > Mct, let's make our scheduling constraint strictly stronger by choosing
N = Mct. So from now on, let's suppose
Mct <= N, and the most frequent tasks are denoted #A, #B, #C, ... #K.
Then we could schedule say, ABC...K__...ABC...K_...ABC...K_....., where A...K occurs
_ denotes idle time, and there is
N space between
A's. This partial schedule would have length
L = (M-1) * (N+1) + Mct. Clearly, we need at least L intervals of time in our schedule to fit our given tasks. Let's show this is enough.
Start inserting the remaining similar tasks in the following 'writing' order:
- The first space to the right of the first K
- The first space to the right of the second K
- The first space to the right of the last K
- The second space to the right of the first K
- The second space to the right of the last K
- The third space to the right of the first K
For example, say we have A B C 1 4 7 10 A B C 2 5 8 11 A B C 3 6 9 12 A B C D.
The numbers denote idle time in the order we will insert.
If we have EEEFFGGHHJJK left, we would insert:
A B C E F G J A B C E F H J A B C E G H K A B C D
Say two tasks of the same type collide if they are scheduled within
N time of each other. After we have inserted all tasks of frequency
M - 1 (which clearly will not collide), other tasks of frequency lower than
M - 1 will never have any task written collide with it's left-neighbor (because of the writing order), and the last task written does not collide with the first task written as they are at least
2N - 1 apart.
len(tasks) <= L, this proves that an
L-length schedule satisfies.
len(tasks) > L, clearly we need at least
len(tasks) intervals of time to schedule all tasks - one interval for each task. Let's insert remaining tasks as before, possibly having one task incomplete. For example, we might have A B C E F G J A B C E F H J A B C E G H K A B C D, with KLLMMNNOO left to insert - and K is incomplete. Our strategy will now be to insert these tasks into our compact schedule.
Our incomplete task (K in our example) can be completed by inserting tasks K in the writing order spots that preceded it. For example, if we wrote J 10th, J 11th, and K 12th, then the positions 11 and 10 are suitable to add K without collision (and numerous enough to permit adding them all). Now with our remaining tasks, say LL, we will insert in the 1st, N+1th, (and 2N+1th, 3N+1th, etc. if necessary) positions in schedule order.
So we've shown that the answer is
This partial schedule would have length L = (M-1) * (N-1) + Mct.
Shouldn't this be
L = (M - 1) * (N+
1) + Mct?
After we have inserted all tasks of frequency Mct - 1 (which clearly will not collide), other tasks of frequency lower than Mct - 1 will never have any task written collide with it's left-neighbor (because of the writing order)
Don't you mean
M - 1, not
Mct - 1?
@bmay Yes, corrected in OP. Thanks
@awice Thanks! I rattled my brain a little bit before I noticed those issues, but your explanation helped a lot!
Here is my solution , to generate schedule along with length of schedule. Generating schedule could be an optional extension of this question
Tasks alternate between run queue and wait queue. Wait queue task moves to run queue when its cooling period has passed. A run queue task gets scheduled and then put on wait queue if it has still some chunks to run.
class Solution(object): def leastInterval(self, tasks, n): """ :type tasks: List[str] :type n: int :rtype: int """ class Task(object): """ Task class to encapsulate notion of task """ def __init__(self, name, count): self.name = name # name of task self.count = -count # number of instances self.time = -1 # time at which it last ran def __repr__(self): return self.name +':' +str(self.count) def schedule(self, time): self.time = time # task is scheduled, update time at which it last ran self.count += 1 # decrease count #def __cmp__(self, other): # cmp(self.count, other.count) def __lt__(self, other): # if two have same count, use the one with lexicographically smaller return self.count < other.count or self.count == other.count and self.name < other.name if n == 0: # if no cooling period, simply return as many tasks as there're return len(tasks) task_collection = collections.Counter(tasks) # count task occurrences cpu_slots =  # a sequence depicting which task runs when runq =  # a run queue, a priority queue waitq = collections.deque() # a wait queue, a simple queue # push all tasks in a run que for name, count in task_collection.items(): heapq.heappush(runq, Task(name, count)) # higher the instances, higher the priority idle_task = Task("idle", 0) # an idle task time = 0 # clock while runq or waitq: # if at least one of the queue has some tasks to run if waitq and ( time - waitq.time ) > n: # if wait queue has task whose cooling period has come heapq.heappush(runq,waitq.popleft()) # put that task in run queue if runq: # schdule highest priority task, if one is ready task = heapq.heappop(runq) task.schedule(time) # consume one instance else: # no task is ready, so schedule idle task task = idle_task cpu_slots.append(task.name) # task scheduled on CPU if task is not idle_task and task.count != 0: waitq.append(task) # if task is not idle task and has at least some instances to run time += 1 return len(cpu_slots) # cpu slots will also print task schedule
The numbers denote idle time in the order we will insert.
Can you explain what you mean by this? I'm really confused by what "A B C 1 4 7 10 A B C 2 5 8 11 A B C 3 6 9 12 A B C D " is. Thanks.
@glang Say we were given input AAAA BBBB CCCC DDD EEE FF GG HH JJ KK, and N = 6.
We can start creating a schedule. A, B, and C occur the most times, so let's place them first. We have to make each task of the same type N = 6 spaces apart.
- A _ _ _ _ _ _ A _ _ _ _ _ _ A _ _ _ _ _ _ A _ _
- A B _ _ _ _ _ A B _ _ _ _ _ A B _ _ _ _ _ A B _
- A B C _ _ _ _ A B C _ _ _ _ A B C _ _ _ _ A B C
Now, we'll just start putting D's, E's, etc. in left to right order similar to how we put the other letters. By our justification above, they won't collide - this will be a valid schedule.
- A B C D _ _ _ A B C D _ _ _ A B C D _ _ _ A B C
- A B C D E _ _ A B C D E _ _ A B C D E _ _ A B C
- A B C D E F _ A B C D E F _ A B C D E _ _ A B C
- A B C D E F G A B C D E F _ A B C D E G _ A B C
- A B C D E F G A B C D E F H A B C D E G H A B C
Now this is a compact schedule, but we might still have stuff left over. We can just place them however we want. In the article there's justification for why this is possible even if say J already occurrs in the compact schedule but isn't exhausted yet.
- J K A B C D E F J K G A B C D E F H A B C D E G H A B C
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.