LeetCode 621. Task Scheduler Greedy Medium Time O(n) Space O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

from collections import defaultdict

class Solution:
    def leastInterval(self, tasks, n: int) -> int:
        if n == 0:
            return len(tasks)

        cd_chrs = defaultdict(int)
        
        output = 0
        i = 0
        while tasks:
            # when reach the end
            if i == len(tasks):
                i = 0
                output += 1 # add 'idle'
                for k in cd_chrs.keys():
                    cd_chrs[k] -= 1
                continue

            if cd_chrs[ tasks[i] ] == 0:
                cd_chrs[ tasks[i] ] = n +1
                tasks.pop(i)
                output += 1
                for k in cd_chrs.keys():
                    cd_chrs[k] -= 1
            else:
                i += 1
            
        return output
# Time Limit Exceeded

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

from collections import defaultdict

class Solution:
    def leastInterval(self, tasks, n: int) -> int:
        if n == 0:
            return len(tasks)

        cd_chrs = defaultdict(int)
        n_chrs = defaultdict(int)
        for _chr in tasks:
            n_chrs[_chr] += 1
        
        output = 0
        zero_size = 0
        while zero_size != len(n_chrs):
            matched = False
            for k in n_chrs.keys():
                if cd_chrs[k] == 0 and n_chrs[k]>0:
                    cd_chrs[k] = n+1
                    n_chrs[k] -= 1
                    if n_chrs[k] == 0:
                        zero_size += 1
                    # if n_chrs[k] == 0:
                    #     del n_chrs[k]
                    # Exception has occurred: RuntimeError
                    # dictionary changed size during iteration
                    output += 1
                    for kk, _ in cd_chrs.items():
                        if cd_chrs[kk] > 0:
                            cd_chrs[kk] -= 1
                        # otherwise                            
                        # defaultdict(<class 'int'>, {'A': -5165, 'B': -5165})
                        # defaultdict(<class 'int'>, {'A': -5165, 'B': -5165})
                    matched = True
            if not matched:
                output += 1 # add 'idle'
                for kk, _ in cd_chrs.items():
                    if cd_chrs[kk] > 0:
                        cd_chrs[kk] -= 1
            
        return output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

# {
#     'A': 3,
#     'B': 3,
#     'C': 3,
#     'D': 2,
#     'E': 1
# }
# n = 3

# [
#     ['A', 'B', 'C', 'D'],
#     ['A', 'B', 'C', 'D'],
#     ['A', 'B', 'C', 'E'],
# ]    
########################################
# {
#     'A': 3,
#     'B': 3,
#     'C': 3,
#     'D': 2,
#     'E': 2
# }
# n = 3

# [
#     ['A', 'B', 'C', 'D'],
#     ['A', 'B', 'C', 'D'],
#     ['A', 'B', 'C', 'E'],
#     ['E'],
# ]   
########################################
# {
#     'A': 3,
#     'B': 3,
#     'C': 3,
#     'D': 2,
#     'E': 1
# }
# n = 2

# [
#     ['A', 'B', 'C']
#     ['A', 'B', 'D']
#     ['A', 'B', 'C']
#     ['D', 'E', 'C']
# ]


from collections import defaultdict, deque
import heapq

class Solution:
    def leastInterval(self, tasks, n: int) -> int:
        if n == 0:
            return len(tasks)
        
        n_tsk = defaultdict(int)
        for tsk in tasks:
            n_tsk[tsk] -= 1
        heap_queu = [v for v in n_tsk.values()]
        # [-1, -3, -2]
        
        heapq.heapify(heap_queu)
        # [-3, -2, -1]

        output = 0
        while heap_queu:
            i = 0
            for _ in range(n+1):
                if not heap_queu:
                    return output

                if i == len(heap_queu):
                    output += 1
                    continue
                
                output += 1
                heap_queu[i] += 1
                if heap_queu[i] == 0:
                    heap_queu.pop(i)
                    continue
                i += 1
        return output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# to find how many idle we need

# n=2
# max=3
# maxct=2

# A _ _ A _ _ A
# A B _ A B _ A B
# A B idle A B idle AB

# ["A","A","A","B","B","B", "C","C","C", "D", "D", "E"]
# n=2
# max=3
# maxct=3
# A _ _ A _ _ A
# A B _ A B _ A B   now we have only 2 
# A B C A B D A B c D E

# output = max(
#     (max-1) * (n+1) + 1*maxct + (others_n - slots),
#     len(tasks)
# )
# where
#     others_n = D D E = 3
#     slots = _ _ = 2

from collections import defaultdict
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        tasks_dict = defaultdict(int)
        for t in tasks:
            tasks_dict[t] += 1
   
        # find max
        _max = 0
        for v in tasks_dict.values():
            if v > _max:
                _max = v
        # find frequence of max
        _maxct = 0
        others_n = 0
        for v in tasks_dict.values():
            if v == _max:
                _maxct += 1
            else:
                others_n += 1
        
        return max(
            (_max-1) * (n+1) + _maxct + max(others_n - max((n+1 -_maxct)*_max, 0), 0),
            len(tasks)
        )
        # Will (others_n - max((n+1 -_maxct)*_max, 0)) be negative?
        #   When slots_n > others_n