621. Task Scheduler - cocoder39/coco39_LC GitHub Wiki

621. Task Scheduler

Option 1 (Preferred)

Thinking process:

Given A, B, A, B, C, A, A, B, B
the max possible idle slots is (freq_max - 1) * n: A, _, _, A, _, _, A, _, _, A
Those idle slots can be filled by B. We can put min(freq_A-1, freq_B): A, B, _, A, B, _, A, B, _, A, B
* where does `freq_A-1` come from? When freq_A == freq_B, only freq_B-1 Bs will be put into those slots and the last B will be put behind the last A
The remaining idle slots can be filled by C: A, B, C, A, B, _, A, B, _, A, B

T = O(1) as there are at most 26 elements to deal with

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freqs = [0] * 26
        for task in tasks:
            index = ord(task) - ord('A')
            freqs[index] += 1
        
        freqs.sort()
        frequ_max = freqs.pop()
        idle_unit = (frequ_max-1) * n
        while freqs:
            idle_unit -= min(frequ_max-1, freqs.pop())
        
        if idle_unit < 0:
            idle_unit = 0
        return idle_unit + len(tasks)

Option 2:

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        earliest_schedule = {task: 0 for task in tasks}
        
        def getCandidateTasks(cur_time):
            res = []
            for t in earliest_schedule:
                if earliest_schedule[t] <= cur_time:
                    res.append(t)
            return res
            
        unit = 0
        counters = collections.Counter(tasks)
        completed_task_count = 0
        while completed_task_count < len(tasks):
            candidates = getCandidateTasks(unit)
            if candidates:
                pick = ''
                pick_count = 0
                for candidate in candidates:
                    if counters[candidate] > pick_count:
                        pick_count = counters[candidate]
                        pick = candidate
                
                counters[pick] -= 1
                completed_task_count += 1
                if counters[pick] == 0:
                    del counters[pick]
                    del earliest_schedule[pick]
                else:
                    earliest_schedule[pick] = unit + 1 + n
            unit += 1
        
        return unit