Python, Straightforward with Explanation


  • 26
    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.

    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).


  • 0
    B

    @awice said in Python, Straightforward with Explanation:

    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?


  • 1

    @bmay Yes, corrected in OP. Thanks


  • 0
    B

    @awice Thanks! I rattled my brain a little bit before I noticed those issues, but your explanation helped a lot!


  • 2
    S

    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[0].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

  • 0
    G

    @awice said in Python, Straightforward with Explanation:

    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.


  • 2

    @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

  • 0
    G

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


  • 0
    F

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


Log in to reply
 

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