We have a list of various types of tasks to perform. Task types are identified with an integral : task of type 1, task of type 2, task of type 3, etc. Each task takes 1 time slot to execute, and once we have executed a task we need cooldown (parameter) time slots to recover before we can execute another task of the same type. However, we can execute tasks of other types in the meantime. The cooldown interval is the same for all task types. We do not reorder the tasks: always execute in order in which we received them on input.
Given a list of input tasks to run, and the cooldown interval, output the number of time slots required to run them.
-
Example 1:
input = [1,1,2,1], n = 2
output = 7 since scheduling become 1-0-0-1-2-0-1 -
Example 2:
input = [1,1,2,3,4,2], n = 3
output = 10 since scheduling become 1-0-0-0-1-2-3-4-0-2 -
Example 3:
input = [1,2,3,4], n = 2
output = 4 since scheduling become 1-2-3-4
def taskScheduler(T, C):
'''
Time Complexity = O(len(input_array))
Space Complexity = O(cooldown_period)
'''
# Base check:
if T is None:
return 0
# task scheduler appended with cooldown period slots initially
result = [0] * C
# set to check if current task is seen previously
seen = set()
# start iterating over the elements
for i in range(len(T)):
# 1. if Task is seen, check if its in the previous C positions
# 2. get index of the current task from previous C positions
# 3. mathematically adjust the number of time, cooldown period
# needs to be appended to my scheduler
print(f"current = {T[i]}")
if T[i] in seen:
if T[i] == result[-1]:
for _ in range(C):
result.append(0)
result.append(T[i])
elif T[i] in result[-C:]:
index = result[-C:].index(T[i])
times = abs(C - i + index + 1)
for _ in range(times):
result.append(0)
result.append(T[i])
else:
result.append(T[i])
else:
# If task is not seen before, simply schedule it
result.append(T[i])
# Add the task into seen
seen.add(T[i])
print(result)
#return len(result) - cooldown period since we added cooldown period initially
return len(result) - C
print(taskScheduler([1,1,2,3,1], 2))
print(taskScheduler([1,2,3,1], 2))
print(taskScheduler([1,1,2,4,3,2], 3))PS: I was asked this question on an actual technical phone screening of a Tier-1 company. I am not sure what level of this question is. But seeking opinions from the community.