---
# System prepended metadata

title: 621. Task Scheduler
tags: [mock interview, 面試]

---

# 621. Task Scheduler


Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
A -> B -> idle -> A -> B -> idle -> A -> B


- Tasks could be done in any order.
- Each task is done in one unit of time.
- n represents the cooldown period between two same tasks.


Return the least number of units of times that the CPU will take to finish all the given tasks.

```
A -> i -> i > A -> i -> i > A 

AAAAAABB
A -> B -> A -> B... -> A


# 1. cnt tasks {A:6, B:6, C:3, D:3} n = 2
# 2. start from most_common task: A B
# 3. check idle count

step 1 -> A..A..A..A..A..A  (6-1)*2 idle seat -> 10
step 2 -> AB.AB.AB.AB.AB.AB  remain 10 - 5
step 3 -> ABCABCABCAB.AB.AB  remain 5 - 3
step 4 -> ABCABCABCABDABDAB  remain 0 + 'D'

step 5 -> ABCABCABCABDABDAB + D -> 18


{A:6, B:6, C:3, D:3, E:3} n = 2
step 1 -> A..A..A..A..A..A 
step 2 -> AB.AB.AB.AB.AB.AB **
step 3 -> ABCABCABCAB.AB.AB
step 4 -> ABCABCABCABDABDAB + D
step 5 -> 'ABCABCABCABDABDABD' +EEE -> 21


{A:6, B:6, C:6, D:6, E:6} n = 2


most common : 6

ABCDE*6

```

```python=

# AABBCCC  n = 1

# C.C.C
# CACAC
# CBACACB

def arrange(tasks, n):
    
    # edge case
    if n == 0:
        return len(tasks)
    
    # cnt tasks and find most common
    taskCount = defultdict(int)
    for task in tasks:
        taskCount[task] += 1
        
    most_common = 0
    for key in taskCount:
        most_common = max(most_common, taskCount[key])
   
    # A B     
    most_common_keys = set()
    for key in taskCount:
        if taskCount[key] == most_common:
            most_common_keys.add(key)
            
    # count idle
    ans = 0
    if n >= len(most_common_keys):
        # n = 1
        #A.A.A
        # n = 2
        # A..A..A
        # still have idle
        
        # AB.AB.AB
        #        (3(A and B) - 1)*(2 - len({AB})+1) = 2
        idles = (most_common-1)*(n-len(most_common_keys)+1)
        
        # AB.AB.AB
        totalTime = idles + len(most_common_keys)*most_common
        
        for key in taskCount:
            if idles > 0 and key not in most_common_keys:
                idles -= taskCount[key]
            else:
                totalTime += taskCount[key]
        if idles < 0:
            totalTime -= idles
            
        ##
        # for key in taskCount:
        #     if key not in most_common_keys:
        #         idles -= taskCount[key]
        # if idles < 0:
        #     totalTime -= idles
        ##
        ans = totalTime
        pass
    else:
        # n = 1
        #ABABAB
        # no idle time
        for key in taskCount:
            ans += taskCount[key]
            
   return ans
    
    
    # count idle time
    
    # handle rest

```

