There are n cores of processor. Each core can process a task at a time. Different cores can process different tasks simultaneously without affecting others. Suppose, there are m tasks in queue and the processor has to process these m tasks. Again, these m tasks are not all of similar type. The type of task is denoted by a number. So, m tasks are represented as m consecutive numbers, same number represents same type of task, like 1 represents task of type 1, 2 for type 2 task and so on.

Initially, all the cores are free. It takes one unit of cost to start a type of task in a core, which is currently not running in that core. One unit cost will be charged at the starting to start tasks on each core. As an example, a core is running type 3 task and if we assign type 3 task again in that core, then cost for this assignment will be zero. But, if we assign type 2 task then cost for this assignment will be one unit. A core keeps processing a task until next task is assigned to that core.

**Example :**

Input : n = 3, m = 6, arr = {1, 2, 1, 3, 4, 1} Output : 4 Input : n = 2, m = 6, arr = {1, 2, 1, 3, 2, 1} Output : 4 Explanation : Input : n = 3, m = 31, arr = {7, 11, 17, 10, 7, 10, 2, 9, 2, 18, 8, 10, 20, 10, 3, 20, 17, 17, 17, 1, 15, 10, 8, 3, 3, 18, 13, 2, 10, 10, 11} Output : 18

**Explanation (for 1st sample I/O) :** Here total number of cores are 3. Let, A, B and C. First assign task of type 1 in any of the cores -> cost 1 unit. States: A – 1, B – None, C – None. Assign task of type 2 in any of the rest 2 cores -> cost 1 unit. States : A – 1, B – 2, C – None. Then assign task of type 1 in that core where task of type 1 is ongoing -> cost 0 unit. States : A – 1, B – 2, C – None.

Assign task of type 3 in the free core -> cost 1 unit. States : A – 1, B – 2, C – 3.

Now, all the cores are running a task. So we have to assign task of type 4 in one of these cores. Let’s load it in the core B, where previously type 2 task was going on -> cost 1 unit.

States: A – 1, B – 4, C – 3. Now, load the type 1 task in the core A, where type 1 task is running -> cost 0 unit. States: A – 1, B – 4, C – 3. Hence, total cost = 1 + 1 + 0 + 1 + 1 + 0 = 4 u

units.

**Explanation 2 (for 2nd sample I/O) :** Total number of cores are 2. Let A and B. First process task of type 1 in any of the cores -> cost 1 unit. States: A – 1, B – None. Process task of type 2 in any of the rest 2 cores -> cost 1 unit. States: A – 1, B – 2. Then process task of type 1 in that core where task of type 1 is ongoing -> cost 0 unit. States : A – 1, B – 2. Now, let’s assign task of type 3 to core A -> cost 1 unit. States : A – 3, B – 2. Now, assign type 2 task in core B, where already type 2 task is going on -> cost 0 unit. States : A – 3, B – 2. Hence, total cost = 1 + 1 + 0 + 1 + 1 = 4 unit. Last assign type 1 task in any of the cores(say A) -> cost 1 unit. States : A – 1, B – 2. Hence, total cost = 1 + 1 + 0 + 1 + 0 + 1 = 4 units.

**Approach :** Dividing this problem into two cases :

First one is when same type of task is currently running in one of the cores. Then, just assign the upcoming task to that core. For example 1, at i = 3(third task), when type 1 task comes then we can assign that task to that core where previously type 1 task was going on. Cost of this is 0 unit.

Second case is when the same type of task is not running in any of the cores. Then, there may be two possibilities. Sub-case 1 is, if there is at least one free core then assign the upcoming task to that core.

Sub-case 2 is, if there are no free core then we have to stop processing one type of task, free up a core and assign the upcoming task in that core such that the cost in future becomes minimum. To minimize cost we should stop one type of task which will never occur again in future. If every ongoing task reoccurs at least once in future, then we should stop that task which will reoccur last among all the currently ongoing tasks(it is a greedy approach and will task).

For example 2 : at i = 4(fourth task), type 3 task, currently ongoing type 1 and type 2 tasks in two cores, we can stop task type 1 or task type 2 to start task type 3. But we will stop task type 1 as type 1 task rehappens after type two task.

## C++

`// C++ Program to fid out minimum ` `// cost to process m tasks ` `#include <bits/stdc++.h> ` ` ` `using` `namespace` `std; ` ` ` `// Function to find out the farthest ` `// position where one of the currently ` `// ongoing tasks will rehappen. ` `int` `find(vector<` `int` `> arr, ` `int` `pos, ` ` ` `int` `m, vector<` `bool` `> isRunning) ` `{ ` ` ` ` ` `// Iterate form last to current ` ` ` `// position and find where the ` ` ` `// task will happen next. ` ` ` `vector<` `int` `> d(m + 1, 0); ` ` ` `for` `(` `int` `i = m; i > pos; i--) ` ` ` `{ ` ` ` `if` `(isRunning[arr[i]]) ` ` ` `d[arr[i]] = i; ` ` ` `} ` ` ` ` ` `// Find out maximum of all these ` ` ` `// positions and it is the ` ` ` `// farthest position. ` ` ` `int` `maxipos = 0; ` ` ` `for` `(` `int` `ele : d) ` ` ` `maxipos = max(ele, maxipos); ` ` ` ` ` `return` `maxipos; ` `} ` ` ` `// Function to find out minimum cost to ` `// process all the tasks ` `int` `mincost(` `int` `n, ` `int` `m, vector<` `int` `> arr) ` `{ ` ` ` ` ` `// freqarr[i][j] denotes the frequency ` ` ` `// of type j task after position i ` ` ` `// like in array {1, 2, 1, 3, 2, 1} ` ` ` `// frequency of type 1 task after ` ` ` `// position 0 is 2. So, for this ` ` ` `// array freqarr[0][1] = 2. Here, ` ` ` `// i can range in between 0 to m-1 and ` ` ` `// j can range in between 0 to m(though ` ` ` `// there is not any type 0 task). ` ` ` `vector<vector<` `int` `> > freqarr(m); ` ` ` ` ` `// Fill up the freqarr vector from ` ` ` `// last to first. After m-1 th position ` ` ` `// frequency of all type of tasks will be ` ` ` `// 0. Then at m-2 th position only frequency ` ` ` `// of arr[m-1] type task will be increased ` ` ` `// by 1. Again, in m-3 th position only ` ` ` `// frequency of type arr[m-2] task will ` ` ` `// be increased by 1 and so on. ` ` ` `vector<` `int` `> newvec(m + 1, 0); ` ` ` `freqarr[m - 1] = newvec; ` ` ` `for` `(` `int` `i = m - 2; i >= 0; i--) ` ` ` `{ ` ` ` `vector<` `int` `> nv; ` ` ` `nv = freqarr[i + 1]; ` ` ` `nv[arr[i + 1]] += 1; ` ` ` `freqarr[i] = nv; ` ` ` `} ` ` ` ` ` `// isRunning[i] denotes whether type i ` ` ` `// task is currently running in one ` ` ` `// of the cores. ` ` ` `// At the beginning no tasks are ` ` ` `// running so all values are false. ` ` ` `vector<` `bool` `> isRunning(m + 1, ` `false` `); ` ` ` ` ` `// cost denotes total cost to assign tasks ` ` ` `int` `cost = 0; ` ` ` ` ` `// truecount denotes number of occupied cores ` ` ` `int` `truecount = 0; ` ` ` ` ` `// iterate through each task and find the ` ` ` `// total cost. ` ` ` `for` `(` `int` `i = 0; i < m; i++) { ` ` ` ` ` `// ele denotes type of task. ` ` ` `int` `ele = arr[i]; ` ` ` ` ` `// Case 1: if smae type of task is ` ` ` `// currently running cost for this ` ` ` `// is 0. ` ` ` `if` `(isRunning[ele] == ` `true` `) ` ` ` `continue` `; ` ` ` ` ` `// Case 2: same type of task is not ` ` ` `// currently running. ` ` ` `else` `{ ` ` ` ` ` `// Subcase 1: if there is at least ` ` ` `// one free core then assign this task ` ` ` `// to that core at a cost of 1 unit. ` ` ` `if` `(truecount < n) { ` ` ` `cost += 1; ` ` ` `truecount += 1; ` ` ` `isRunning[ele] = ` `true` `; ` ` ` `} ` ` ` ` ` `// Subcase 2: No core is free ` ` ` `else` `{ ` ` ` ` ` `// here we will first find the minimum ` ` ` `// frequency among all the ongoing tasks ` ` ` `// in future. ` ` ` `// If the minimum frequency is 0 then ` ` ` `// there is at least one ongoing task ` ` ` `// which will not occur again. Then we just ` ` ` `// stop tha task. ` ` ` `// If minimum frequency is >0 then, all the ` ` ` `// tasks will occur at least once in future. ` ` ` `// we have to find out which of these will ` ` ` `// rehappen last among the all ongoing tasks. ` ` ` ` ` `// set minimum frequency to a big number ` ` ` `int` `mini = 100000; ` ` ` ` ` `// set index of minimum frequency task to 0. ` ` ` `int` `miniind = 0; ` ` ` ` ` `// find the minimum frequency task type(miniind) ` ` ` `// and frequency(mini). ` ` ` `for` `(` `int` `j = 1; j <= m; j++) { ` ` ` `if` `(isRunning[j] && mini > freqarr[i][j]) { ` ` ` `mini = freqarr[i][j]; ` ` ` `miniind = j; ` ` ` `} ` ` ` `} ` ` ` ` ` `// If minimum frequency is zero then just stop ` ` ` `// the task and start the present task in that ` ` ` `// core. Cost for this is 1 unit. ` ` ` `if` `(mini == 0) { ` ` ` `isRunning[miniind] = ` `false` `; ` ` ` `isRunning[ele] = ` `true` `; ` ` ` `cost += 1; ` ` ` `} ` ` ` ` ` `// If minimum frequency is nonzero then find ` ` ` `// the farthest position where one of the ` ` ` `// ongoing task will rehappen. ` ` ` `// Stop that task and start present task ` ` ` `// in that core. ` ` ` `else` `{ ` ` ` ` ` `// find out the farthest position using ` ` ` `// find function ` ` ` `int` `farpos = find(arr, i, m, isRunning); ` ` ` `isRunning[arr[farpos]] = ` `false` `; ` ` ` `isRunning[ele] = ` `true` `; ` ` ` `cost += 1; ` ` ` `} ` ` ` `} ` ` ` `} ` ` ` `} ` ` ` `// return total cost ` ` ` `return` `cost; ` `} ` ` ` `// Driver Program ` `int` `main() ` `{ ` ` ` `// Test case 1 ` ` ` `int` `n1 = 3; ` ` ` `int` `m1 = 6; ` ` ` `vector<` `int` `> arr1{ 1, 2, 1, 3, 4, 1 }; ` ` ` `cout << mincost(n1, m1, arr1) << endl; ` ` ` ` ` `// Test case 2 ` ` ` `int` `n2 = 2; ` ` ` `int` `m2 = 6; ` ` ` `vector<` `int` `> arr2{ 1, 2, 1, 3, 2, 1 }; ` ` ` `cout << mincost(n2, m2, arr2) << endl; ` ` ` ` ` `// Test case 3 ` ` ` `int` `n3 = 3; ` ` ` `int` `m3 = 31; ` ` ` `vector<` `int` `> arr3{ 7, 11, 17, 10, 7, 10, 2, 9, ` ` ` `2, 18, 8, 10, 20, 10, 3, 20, ` ` ` `17, 17, 17, 1, 15, 10, 8, 3, ` ` ` `3, 18, 13, 2, 10, 10, 11 }; ` ` ` `cout << mincost(n3, m3, arr3) << endl; ` ` ` ` ` `return` `0; ` `} ` |

## Python3

# Python3 Program to fid out

# minimum cost to process m tasks

# Function to find out the farthest

# position where one of the currently

# ongoing tasks will rehappen.

def find(arr, pos, m, isRunning):

# Iterate form last to current

# position and find where the

# task will happen next.

d = [0] * (m + 1)

for i in range(m – 1, pos, -1):

if isRunning[arr[i]]:

d[arr[i]] = i

# Find out maximum of all these positions

# and it is the farthest position.

maxipos = 0

for ele in d:

maxipos = max(ele, maxipos)

return maxipos

# Function to find out minimum

# cost to process all the tasks

def mincost(n, m, arr):

# freqarr[i][j] denotes the frequency

# of type j task after position i

# like in array 1, 2, 1, 3, 2, 1

# frequency of type 1 task after

# position 0 is 2. So, for this

# array freqarr[0][1] = 2. Here,

# i can range in between 0 to m-1 and

# j can range in between 0 to m(though

# there is not any type 0 task).

freqarr = [[] for i in range(m)]

# Fill up the freqarr vector from

# last to first. After m-1 th position

# frequency of all type of tasks will be

# 0. Then at m-2 th position only frequency

# of arr[m-1] type task will be increased

# by 1. Again, in m-3 th position only

# frequency of type arr[m-2] task will

# be increased by 1 and so on.

newvec = [0] * (m + 1)

freqarr[m – 1] = newvec[:]

for i in range(m – 2, -1, -1):

nv = freqarr[i + 1][:]

nv[arr[i + 1]] += 1

freqarr[i] = nv[:]

# isRunning[i] denotes whether type i

# task is currently running in one

# of the cores.

# At the beginning no tasks are

# running so all values are false.

isRunning = [False] * (m + 1)

# cost denotes total cost to assign tasks

cost = 0

# truecount denotes number of occupied cores

truecount = 0

# iterate through each task

# and find the total cost.

for i in range(0, m):

# ele denotes type of task.

ele = arr[i]

# Case 1: if smae type of task is

# currently running cost for this is 0.

if isRunning[ele] == True:

continue

# Case 2: same type of task

# is not currently running.

else:

# Subcase 1: if there is at least

# one free core then assign this task

# to that core at a cost of 1 unit.

if truecount < n:
cost += 1
truecount += 1
isRunning[ele] = True
# Subcase 2: No core is free
else:
# here we will first find the minimum
# frequency among all the ongoing tasks
# in future.
# If the minimum frequency is 0 then
# there is at least one ongoing task
# which will not occur again. Then we just
# stop tha task.
# If minimum frequency is >0 then, all the

# tasks will occur at least once in future.

# we have to find out which of these will

# rehappen last among the all ongoing tasks.

# set minimum frequency to a big number

mini = 100000

# set index of minimum frequency task to 0.

miniind = 0

# find the minimum frequency task

# type(miniind) and frequency(mini).

for j in range(1, m + 1):

if isRunning[j] and mini > freqarr[i][j]:

mini = freqarr[i][j]

miniind = j

# If minimum frequency is zero then just stop

# the task and start the present task in that

# core. Cost for this is 1 unit.

if mini == 0:

isRunning[miniind] = False

isRunning[ele] = True

cost += 1

# If minimum frequency is nonzero then find

# the farthest position where one of the

# ongoing task will rehappen.

# Stop that task and start present task

# in that core.

else:

# find out the farthest position

# using find function

farpos = find(arr, i, m, isRunning)

isRunning[arr[farpos]] = False

isRunning[ele] = True

cost += 1

# return total cost

return cost

# Driver Code

if __name__ == “__main__”:

# Test case 1

n1, m1 = 3, 6

arr1 = [1, 2, 1, 3, 4, 1]

print(mincost(n1, m1, arr1))

# Test case 2

n2, m2 = 2, 6

arr2 = [1, 2, 1, 3, 2, 1]

print(mincost(n2, m2, arr2))

# Test case 3

n3, m3 = 3, 31

arr3 = [7, 11, 17, 10, 7, 10, 2, 9,

2, 18, 8, 10, 20, 10, 3, 20,

17, 17, 17, 1, 15, 10, 8, 3,

3, 18, 13, 2, 10, 10, 11]

print(mincost(n3, m3, arr3))

# This code is contributed by Rituraj Jain

**Output:**

4 4 18

**Time Complexity : **O(m^2)

**Space Complexity : **O(m^2), (to store the freqarr)

## leave a comment

## 0 Comments