621. Task Scheduler

from heapq import heappush, heappop
class Solution:
# time(N) space O(N)
    def leastInterval(self, tasks: List[str], n: int) -> int:
        size = len(tasks)
        if not n:
            return size
        # step1: count times of each task, get the task with max 
        cnt = collections.Counter(tasks)
        # step2: push cnt,task into PQ 
        hp,cur_time = [],0
        for task,ct in cnt.items():
            heappush(hp,(-ct,task))
            
        #step3: running heap until tasks inside runs out
        while hp:
            # why tmp list: make sure task with same cnt will not conflict each other 
            idx,tmp = 0, []
            # idx: mark position at single interval  => A _ _ , n = 2, idx= 0, 1, 2 
            # step4: for each valid slot set(minimum at n interval ), each time do heap operation, increment time by 1
            while idx <= n:
                # cur_time record assigned task length so far
                cur_time += 1
                if hp:
                    # step4.1: pop out task and its cnt off PQ
                    time, taskid = heappop(hp)
                    # step4.2 check if cnt for taskid has run out, if not, push task and updated ask to tmp list 
                    if time != -1:
                        tmp.append((time+1,taskid))
                # step4.3 check if hp and tmp run out , if not idx + 1 
                if not hp and not tmp:
                    break
                # here is to guaranteen each task has interval n .  e.g. hp: [] tmp:[(-2,A)] and before push (-2,A) back to hq, need to make sure idx has reached to n 
                else:
                    idx += 1
            # step5: push updated task and cnt back to hp, reset idx and tmp, go to next loop again
            for item in tmp:
                heappush(hp,item)
        # step6, return current time 
        return cur_time
                    

class Solution:
    # time O(N) space O(1) since 26 ~ 1
    def leastInterval(self, tasks: List[str], n: int) -> int:
        feq = [0] *26
        for t in tasks:
            feq[ord(t)-ord('A')] += 1
        feq.sort()
        frq_max = feq.pop() 
        idle_slots = (frq_max - 1) * n
        while feq:
            # why frq_max -1 ?  because freq.pop() <= frq_max; if freq.pop() ==  frq_max , the task just need to ocupy frq_max-1 since last task will idle always.  
            idle_slots -= min(feq.pop(),frq_max-1)
        idle_slots  = max(0,idle_slots)
        return len(tasks) + idle_slots