Home/

...

/

Problem Challenge 2

Problem Challenge 2

Resources for scheduling tasks on a server.

Problem statement

You are given a list of tasks that need to be run, in any order, on a server. Each task will take one CPU interval to execute but once a task has finished, it has a cooling period during which it can’t be run again. If the cooling period for all tasks is ‘K’ intervals, find the minimum number of CPU intervals that the server needs to finish all tasks.

If at any time the server can’t execute any task then it must stay idle.

Dry-run templates

This is the implementation of the solution provided in the lesson:

Press + to interact
Python 3.5
from heapq import *
def schedule_tasks(tasks, k):
  intervalCount = 0
  taskFrequencyMap = {}
  for char in tasks:
    taskFrequencyMap[char] = taskFrequencyMap.get(char, 0) + 1
  maxHeap = []
  # add all tasks to the max heap
  for char, frequency in taskFrequencyMap.items():
    heappush(maxHeap, (-frequency, char))
  while maxHeap:
    waitList = []
    n = k + 1  # try to execute as many as 'k+1' tasks from the max-heap
    while n > 0 and maxHeap:
      intervalCount += 1
      frequency, char = heappop(maxHeap)
      if -frequency > 1:
        # decrement the frequency and add to the waitList
        waitList.append((frequency+1, char))
      n -= 1
    # put all the waiting list back on the heap
    for frequency, char in waitList:
      heappush(maxHeap, (frequency, char))
    if maxHeap:
      intervalCount += n  # we'll be having 'n' idle intervals for the next iteration
  return intervalCount
def main():
  print("Minimum intervals needed to execute all tasks: " +
        str(schedule_tasks(['a', 'a', 'a', 'b', 'c', 'c'], 2)))
  print("Minimum intervals needed to execute all tasks: " +
        str(schedule_tasks(['a', 'b', 'a'], 3)))
main()

This problem follows the top ‘K’ elements pattern. We need to rearrange tasks such that the same tasks are ‘K’ distance apart.

Consider an example where tasks are [a,a,b,c,c][a,a,b,c,c] and k is 2. This means, that the same task cannot execute before 2 CPU intervals. Therefore, the scheduling for the above tasks would be: a−>c−>b−>a−>ca -> c -> b -> a -> c. As evident, after the first aa, the next aa is scheduled after two tasks, that is, after two CPU intervals.

However, if the given tasks were [a,a][a,a] and k was still 2, the scheduling would be a−>idle−>idle−>aa -> idle -> idle -> a, instead.

Sample input #1

Input: [a, a, a, b, c, c], K=2

Note: The first for loop populates the taskFrequencyMap dictionary with tasks and their frequencies. The second for loop pushes them to the heap. Our table below does not show the iterations for these loops. The outer iteration column refers to the while loop in our code, inner while loop iteration refers to the nested while loop, and the inner for loop iteration to the nested for loop.

Lines 6-8 in the above code populate our taskFrequencyMap dictionary with the tasks and their frequencies. For this example, the dictionary will be {'a': 3, 'b': 1, 'c': 2}. This step is not shown in the table below.

Outer iteration

Inner while loop iteration

Inner for loop iteration

Line number

MaxHeap

n

interval

count

waitList

-

-

-

5, 6, 10

[]

-

0

-

-

-

-

7-8

[]

-

0

-

-

-

-

12-13

[(-3, 'a'), (-1, 'b'), (-2, 'c')]

-

0

-

1

-

-

16-17

[(-3, 'a'), (-1, 'b'), (-2, 'c')]

3

0

[]

1

1

-

17-24

[(-2, 'c'), (-1, 'b')]

2

1

[(-2, 'a')]

1

2

-

17-24

[(-1, 'b')]

1

2

[(-2, 'a'), (-1, 'c')]

1

3

-

17-24

[]

0

3

[(-2, 'a'), (-1, 'c')]

1

-

1

27-28

[(-2, 'a')]

0

3

[(-2, 'a'), (-1, 'c')]

1

-

2

27-28

[(-2, 'a'), (-1, 'c')]

0

3

[(-2, 'a'), (-1, 'c')]

1

-

-

30-31

[(-2, 'a'), (-1, 'c')]

0

3

[(-2, 'a'), (-1, 'c')]

2

-

-

16-17

[(-2, 'a'), (-1, 'c')]

3

3

[]

2

1

-

17-24

[(-1, 'c')]

2

4

[(-1, 'a')]

2

2

-

17-24

[]

1

5

[(-1, 'a')]

2

-

1

27-28

[(-1, 'a')]

1

6

[(-1, 'a')]

3

-

-

16-17

[(-1, 'a')]

3

6

[]

3

1

-

17-24

[]

2

7

[]

Sample input #2

Input: [a, b, a], K=3

Lines 6-8 in the above code populate our taskFrequencyMap dictionary with the tasks and their frequencies. For this example, the dictionary will be {'a': 2, 'b': 1}. This step is not shown in the table below.

Outer iteration

Inner while loop iteration

Inner for loop iteration

Line number

MaxHeap

n

interval

count

waitList

-

-

-

5, 6, 10

[]

-

0

-

-

-

-

12-13

[(-2, 'a'), (-1, 'b')]

-

0

-

1

-

-

16-17

[(-2, 'a'), (-1, 'b')]

4

0

[]

1

1

-

17-24

[(-1, 'b')]

3

1

[(-1, 'a')]

1

2

-

17-24

[]

2

2

[(-1, 'a')]

1

-

1

27-28

[(-1, 'a')]

2

2

[(-1, 'a')]

1

-

-

30-31

[(-1, 'a')]

2

4

[(-1, 'a')]

2

-

-

16-17

[(-1, 'a')]

4

4

[]

2

1

-

17-24

[]

3

5

[]

Step-by-step solution construction

Here’s what we’ll be doing:

  • We will use a Max Heap to execute the highest frequency task first.
  • After executing a task we decrease its frequency and put it on a waiting list.
  • In each iteration, we will try to execute as many as k+1 tasks.
  • For the next iteration, we will put all the waiting tasks back in the Max Heap.
  • If for any iteration, we are not able to execute k+1 tasks, the CPU has to remain idle for the remaining time in the next iteration.

The first step is to populate our taskFrequencyMap dictionary with the tasks and their frequencies. We use the get function to get a task’s frequency from the dictionary and update its value by incrementing it by 1.

Press + to interact
Python 3.5
from heapq import *
def schedule_tasks(tasks, k):
  print("Given tasks: ", tasks)
  print("Given interval: ", k)
  print("")
  intervalCount = 0
  taskFrequencyMap = {}
  i = 1
  print("Populating our frequency dictionary.")
  for char in tasks:
    print("\tLoop iteration: ", i, sep = "")
    print("\t\tTask: ", char, sep="")
    taskFrequencyMap[char] = taskFrequencyMap.get(char, 0) + 1
    print("\t\ttaskFrequencyMap: ", taskFrequencyMap, "\n", sep = "")
def main():
  input = [(['a', 'a', 'a', 'b', 'c', 'c'], 2), (['a', 'b', 'a'], 3)]
  for i in input:
    print("Minimum intervals needed to execute all tasks: " +
        str(schedule_tasks(i[0], i[1])))
    print("-"*100, "\n", sep="")
main()

The next step is to push the tasks and their frequencies to our maxHeap. We’ll add them as tuples and since we’re maintaining a max heap, we’ll make the frequencies negative. The heapq library will use the first element of the tuple as the key for organizing the tuples as a heap. This way, we’ll always have the largest frequency at the top of the heap, that is, its first value.

Press + to interact
Python 3.5
from heapq import *
def schedule_tasks(tasks, k):
  print("Given tasks: ", tasks)
  print("Given interval: ", k)
  print("")
  intervalCount = 0
  taskFrequencyMap = {}
  i = 1
  print("Populating our frequency dictionary.")
  for char in tasks:
    print("\tLoop iteration: ", i, sep = "")
    print("\t\tTask: ", char, sep="")
    taskFrequencyMap[char] = taskFrequencyMap.get(char, 0) + 1
    print("\t\ttaskFrequencyMap: ", taskFrequencyMap, "\n", sep = "")
  
  maxHeap = []
  # add all tasks to the max heap
  j = 1
  print("Populating our maxHeap.")
  for char, frequency in taskFrequencyMap.items():
    print("\tLoop iteration: ", j, sep = "")
    j+=1
    print("\t\tPushing (", frequency, ", ", char, ") into the heap.", sep = "")
    heappush(maxHeap, (-frequency, char))
    print("\t\tMaxHeap: ", maxHeap, "\n", sep = "")
def main():
  input = [(['a', 'a', 'a', 'b', 'c', 'c'], 2), (['a', 'b', 'a'], 3)]
  for i in input:
    print("Minimum intervals needed to execute all tasks: " +
        str(schedule_tasks(i[0], i[1])))
    print("-"*100, "\n", sep="")
main()

Next, we’ll start executing our tasks and pushing them into the waitlist if there are multiple occurrences. We’ll try to execute k+1 tasks. We’ll pop the task from our maxHeap since now we’ll have one less task to consider.

If a task’s frequency is greater than 1, we’ll execute it once and then decrement its frequency to append to the waitlist. This is because the same task cannot execute before k intervals and now has to wait. Lastly, we’ll decrement our n since now we have one less task to execute.

Press + to interact
Python 3.5
from heapq import *
def schedule_tasks(tasks, k):
  print("Given tasks: ", tasks)
  print("Given interval: ", k)
  print("")
  intervalCount = 0
  taskFrequencyMap = {}
  i = 1
  print("Populating our frequency dictionary.")
  for char in tasks:
    print("\tLoop iteration: ", i, sep = "")
    print("\t\tTask: ", char, sep="")
    taskFrequencyMap[char] = taskFrequencyMap.get(char, 0) + 1
    print("\t\ttaskFrequencyMap: ", taskFrequencyMap, "\n", sep = "")
  
  maxHeap = []
  # add all tasks to the max heap
  j = 1
  print("Populating our maxHeap.")
  for char, frequency in taskFrequencyMap.items():
    print("\tLoop iteration: ", j, sep = "")
    j+=1
    print("\t\tPushing (", frequency, ", ", char, ") into the heap.", sep = "")
    heappush(maxHeap, (-frequency, char))
    print("\t\tMaxHeap: ", maxHeap, "\n", sep = "")
  while maxHeap:
    waitList = []
    n = k + 1  # try to execute as many as 'k+1' tasks from the max-heap
    print("We'll try to execute as many as ", k + 1, " tasks." , sep = "")
    x = 1
    while n > 0 and maxHeap:
      print("\tLoop iteration: ", x, sep = "")
      x+=1
      intervalCount += 1
      frequency, char = heappop(maxHeap)
      print("\t\t(", frequency, ", ", char, ") popped from the heap.", sep ="")
      if -frequency > 1:
        # decrement the frequency and add to the waitList
        print("\t\tSince the frequency of the task is greater than 1, decrementing it and appending to our waitlist.")
        waitList.append((frequency+1, char))
      else:
        print("\t\tSince the frequency of our task was 1, we don't need to append it to our waitlist.")
      n -= 1
      print("\t\tWaitlist: ", waitList, "\n", sep = "")
def main():
  input = [(['a', 'a', 'a', 'b', 'c', 'c'], 2), (['a', 'b', 'a'], 3)]
  for i in input:
    print("Minimum intervals needed to execute all tasks: " +
        str(schedule_tasks(i[0], i[1])))
    print("-"*100, "\n", sep="")
main()

Once our maxHeap is empty, this means we’ve executed our tasks one time and the remaining have been appended to the waitlist. The next step is to now put back the waitlisted tasks in the heap to be executed again.

Press + to interact
Python 3.5
from heapq import *
def schedule_tasks(tasks, k):
  print("Given tasks: ", tasks)
  print("Given interval: ", k)
  print("")
  intervalCount = 0
  taskFrequencyMap = {}
  i = 1
  print("Populating our frequency dictionary.")
  for char in tasks:
    print("\tLoop iteration: ", i, sep = "")
    print("\t\tTask: ", char, sep="")
    taskFrequencyMap[char] = taskFrequencyMap.get(char, 0) + 1
    print("\t\ttaskFrequencyMap: ", taskFrequencyMap, "\n", sep = "")
  
  maxHeap = []
  # add all tasks to the max heap
  j = 1
  print("Populating our maxHeap.")
  for char, frequency in taskFrequencyMap.items():
    print("\tLoop iteration: ", j, sep = "")
    j+=1
    print("\t\tPushing (", frequency, ", ", char, ") into the heap.", sep = "")
    heappush(maxHeap, (-frequency, char))
    print("\t\tMaxHeap: ", maxHeap, "\n", sep = "")
  while maxHeap:
    waitList = []
    n = k + 1  # try to execute as many as 'k+1' tasks from the max-heap
    print("We'll try to execute as many as ", k + 1, " tasks." , sep = "")
    x = 1
    while n > 0 and maxHeap:
      print("\tLoop iteration: ", x, sep = "")
      x+=1
      intervalCount += 1
      frequency, char = heappop(maxHeap)
      print("\t\t(", frequency, ", ", char, ") popped from the heap.", sep ="")
      if -frequency > 1:
        # decrement the frequency and add to the waitList
        print("\t\tSince the frequency of the task is greater than 1, decrementing it and appending to our waitlist.")
        waitList.append((frequency+1, char))
      else:
        print("\t\tSince the frequency of our task was 1, we don't need to append it to our waitlist.")
      n -= 1
      print("\t\tWaitlist: ", waitList, "\n", sep = "")
    # put all the waiting list back on the heap
    print("Pushing back our waitlisted tasks to the heap.")
    print("Waitlist: ", waitList, sep = "")
    c = 1
    for frequency, char in waitList:
      print("\tLoop iteration: ", c, sep = "")
      c+=1
      print("\t\tPushing (", frequency, ", ", char, ") to the heap.", sep = "")
      heappush(maxHeap, (frequency, char))
      print("\t\tmaxHeap: ", maxHeap, "\n", sep = "")
def main():
  input = [(['a', 'a', 'a', 'b', 'c', 'c'], 2), (['a', 'b', 'a'], 3)]
  for i in input:
    print("Minimum intervals needed to execute all tasks: " +
        str(schedule_tasks(i[0], i[1])))
    print("-"*100, "\n", sep="")
main()

Lastly, we’ll add an if condition to check if there are still tasks remaining in our maxHeap. If yes, we’ll increment our interval count by n. That is, we’ll be having n idle intervals for the next iteration.

We’ll continue in the same loop until our waitlist and max heap are empty. That is, all tasks have been executed. Then, we’ll return the final interval count.

Press + to interact
Python 3.5
from heapq import *
orderlist = []
def schedule_tasks(tasks, k):
  print("Given tasks: ", tasks)
  print("Given interval: ", k)
  print("")
  intervalCount = 0
  taskFrequencyMap = {}
  i = 1
  print("Populating our frequency dictionary.")
  for char in tasks:
    print("\tLoop iteration: ", i, sep = "")
    print("\t\tTask: ", char, sep="")
    taskFrequencyMap[char] = taskFrequencyMap.get(char, 0) + 1
    print("\t\ttaskFrequencyMap: ", taskFrequencyMap, "\n", sep = "")
  
  maxHeap = []
  # add all tasks to the max heap
  j = 1
  print("Populating our maxHeap.")
  for char, frequency in taskFrequencyMap.items():
    print("\tLoop iteration: ", j, sep = "")
    j+=1
    print("\t\tPushing (", frequency, ", ", char, ") into the heap.", sep = "")
    heappush(maxHeap, (-frequency, char))
    print("\t\tMaxHeap: ", maxHeap, "\n", sep = "")
  while maxHeap:
    waitList = []
    n = k + 1  # try to execute as many as 'k+1' tasks from the max-heap
    print("We'll try to execute as many as ", k + 1, " tasks." , sep = "")
    x = 1
    while n > 0 and maxHeap:
      print("\tLoop iteration: ", x, sep = "")
      x+=1
      intervalCount += 1
      frequency, char = heappop(maxHeap)
      global orderlist
      orderlist.append(char)
      
      print("\t\t(", frequency, ", ", char, ") popped from the heap.", sep ="")
      if -frequency > 1:
        # decrement the frequency and add to the waitList
        print("\t\tSince the frequency of the task is greater than 1, decrementing it and appending to our waitlist.")
        waitList.append((frequency+1, char))
        print("\t\tWaitlist: ", waitList, "\n", sep = "")
      else:
        print("\t\tSince the frequency of our task was 1, we don't need to append it to our waitlist.")
      n -= 1
      print("\t\tWaitlist: ", waitList, "\n", sep = "")
    # put all the waiting list back on the heap
    print("Pushing back our waitlisted tasks to the heap.")
    print("Waitlist: ", waitList, sep = "")
    c = 1
    for frequency, char in waitList:
      print("\tLoop iteration: ", c, sep = "")
      c+=1
      print("\t\tPushing (", frequency, ", ", char, ") to the heap.", sep = "")
      heappush(maxHeap, (frequency, char))
      print("\t\tmaxHeap: ", maxHeap, "\n", sep = "")
    if maxHeap:
      print("Our max heap is not empty, hence, we'll increment our interval count by n = ", str(n), ".", sep="")
      intervalCount += n  # we'll be having 'n' idle intervals for the next iteration
      for i in range(n):
        orderlist.append("idle")
      print("\tInterval count: ", intervalCount, "\n", sep = "")
    else:
      print("Our max heap is empty, no more tasks to execute!\n")
  return intervalCount
def main():
  input = [(['a', 'a', 'a', 'b', 'c', 'c'], 2), (['a', 'b', 'a'], 3)]
  for i in input:
    print("Minimum intervals needed to execute all tasks: " +
        str(schedule_tasks(i[0], i[1])))
    outputstr = ""
    global orderlist
    for i in orderlist:
      outputstr += i + " --> "
    print("Order of task execution: ", outputstr[:-5])
    print("-"*100, "\n", sep="")
    orderlist.clear()
main()