unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 621: Task Scheduler

link

Note len(tasks)is the lower bound for interval count. If all tasks are distinct, scheduling them in any order achieves the lower bound. However, when some tasks are repeated, we may need to insert idle cycles to cool the CPU down. With repeated tasks, if possible, we should put two instances of the same task n intervals apart, so we do not need to insert idle cycles.

We thus process the tasks in decreasing order of their frequency or instance count. We try making groups of (n+1) distinct tasks. Two such groups do not need any idle cycle in-between.

Say there are total \tau tasks with \delta of them distinct.

Time: \mathcal{O}(\tau \cdot \lg{\delta}), space: \mathcal{O}(\delta).

from heapq import heapify, heappush as push, heappop as pop

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count_of = {}
        for t in tasks:
            if t not in count_of:
                count_of[t] = 1
            else:
                count_of[t] += 1
        
        maxq = [(-count, t) for t, count in count_of.items()]
        heapify(maxq)

        interval = 0
        while maxq:
            group = []
            while maxq and len(group) < n+1:
                group.append( pop(maxq) )
            interval += len(group)
            
            for neg_count, t in group:
                count = -neg_count
                count -= 1
                if count > 0:
                    push(maxq, (-count, t))

            if maxq:
                idle_count = (n+1) - len(group)
                interval += idle_count

        return interval

tanvirdotzaman

,

Leave a comment