# Python, Straightforward with Explanation

• ``````def leastInterval(self, tasks, N):
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.

When `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 `Mct` times, `_` 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.

If `len(tasks) <= L`, this proves that an `L`-length schedule satisfies.

When `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 `max(len(tasks), L)`.

• 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):
"""
:type n: int
:rtype: int
"""
"""
"""
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

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
heapq.heappush(runq, Task(name, count))  # higher the instances, higher the priority

time = 0                    # clock
while runq or waitq:        # if at least one of the queue has some tasks to run

if waitq and ( time - waitq[0].time ) > n:  # if wait queue has task whose cooling period has come
heapq.heappush(runq,waitq.popleft())    # put that task in run queue

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

• @awice Thanks for the quick reply! The visualization helps tremendously.

• @awice So cool! But I do think this is not a programming skillðŸ˜‚ It depends on your strong math and analytical skills!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.