-
Notifications
You must be signed in to change notification settings - Fork 0
/
621-task-scheduler.py
90 lines (63 loc) · 2.76 KB
/
621-task-scheduler.py
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
84
85
86
87
88
89
90
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
if n == 0:
return len(tasks)
# create cooling and ready maps for tasks A-Z
cooling, counter = [0] * 26, [0] * 26
# populate counter map
for task in tasks:
counter[ord(task) - ord('A')] += 1
# having a non zero in cooling means tasks X is unavailable
# greedy strategy, always choose the most frequent tasks to allow it to cool
# create total amount of cycles counter
t = 0
# create tasksLeft
tasksLeft = len(tasks)
while tasksLeft > 0:
# get most frequent task index and counter
nextTask, maxCount = -1, 0
# iterate through tasks A-Z
for i in range(26):
# if cooling, decrement cooling counter
if cooling[i] > 0:
cooling[i] -= 1
# or else tasks is ready and check for most frequent tasks
elif counter[i] > 0:
if counter[i] > maxCount:
maxCount = counter[i]
nextTask = i
# if there is an available task
if nextTask != -1:
# cool task
cooling[nextTask] = n
# decrement task count
counter[nextTask] -= 1
# decrement total tasks
tasksLeft -= 1
# increment cycles
t += 1
return t
# Smart solution with some counting
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
# find task(s) with greatest frequency
count = [0] * 26
for task in tasks:
count[ord(task) - ord('A')] += 1
maxCount = max(count)
# get number of tasks with same max freq
numOfMaxCount = 0
for frequency in count:
if frequency == maxCount:
numOfMaxCount += 1
# get number of rests needed between max tasks
numOfIntervals = maxCount-1
# get length of each rest period
intervalLength = n - numOfMaxCount + 1
# get number of cycles in each rest. If multiple maxes, each rest gets eaten up by remaining maxes
restCycles = numOfIntervals * intervalLength
# get remaining tasks
remainingTaskCount = len(tasks) - maxCount * numOfMaxCount
# if total restCycles is greater than remainder task count, some rest periods are needed. if lesser, than all tasks can be run with no breaks
requiredRestCycles = max(0, restCycles - remainingTaskCount)
return len(tasks) + requiredRestCycles