Hay n núcleos de procesador. Cada núcleo puede procesar una tarea a la vez. Diferentes núcleos pueden procesar diferentes tareas simultáneamente sin afectar a otros. Supongamos que hay m tareas en cola y el procesador tiene que procesar estas m tareas. De nuevo, estas m tareas no son todas del mismo tipo. El tipo de tarea se indica con un número. Entonces, m tareas se representan como m números consecutivos, el mismo número representa el mismo tipo de tarea, como 1 representa la tarea de tipo 1, 2 para la tarea de tipo 2 y así sucesivamente.
Inicialmente, todos los núcleos son gratuitos. Se necesita una unidad de costo para iniciar un tipo de tarea en un núcleo, que actualmente no se está ejecutando en ese núcleo. Se cobrará un costo unitario al inicio de las tareas de inicio en cada núcleo. Como ejemplo, un núcleo ejecuta una tarea de tipo 3 y si volvemos a asignar una tarea de tipo 3 en ese núcleo, el costo de esta asignación será cero. Pero, si asignamos la tarea de tipo 2, el costo de esta asignación será una unidad. Un núcleo continúa procesando una tarea hasta que se asigna la siguiente tarea a ese núcleo.
Ejemplo :
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
Explicación (para la primera muestra de E/S): aquí el número total de núcleos es 3. Sea A, B y C. Primero asigne una tarea de tipo 1 en cualquiera de los núcleos -> cueste 1 unidad. Estados: A – 1, B – Ninguno, C – Ninguno. Asigne tarea de tipo 2 en cualquiera de los 2 núcleos restantes -> costo 1 unidad. Estados: A – 1, B – 2, C – Ninguno. Luego asigne la tarea de tipo 1 en ese núcleo donde la tarea de tipo 1 está en curso -> unidad de costo 0. Estados: A – 1, B – 2, C – Ninguno.
Asignar tarea de tipo 3 en el núcleo libre -> cuesta 1 unidad. Estados: A – 1, B – 2, C – 3.
Ahora, todos los núcleos están ejecutando una tarea. Entonces tenemos que asignar una tarea de tipo 4 en uno de estos núcleos. Carguémoslo en el núcleo B, donde anteriormente se estaba realizando la tarea de tipo 2 -> costaba 1 unidad.
Estados: A – 1, B – 4, C – 3. Ahora, cargue la tarea de tipo 1 en el núcleo A, donde se está ejecutando la tarea de tipo 1 -> unidad de costo 0. Estados: A – 1, B – 4, C – 3. Por lo tanto, costo total = 1 + 1 + 0 + 1 + 1 + 0 = 4 u
unidades.
Explicación 2 (para la segunda muestra de E/S): el número total de núcleos es 2. Sean A y B. Primera tarea de proceso de tipo 1 en cualquiera de los núcleos -> costo 1 unidad. Estados: A – 1, B – Ninguno. Tarea de proceso de tipo 2 en cualquiera de los 2 cores restantes -> cuesta 1 unidad. Estados: A – 1, B – 2. Luego, procese la tarea de tipo 1 en ese núcleo donde la tarea de tipo 1 está en curso -> cuesta 0 unidad. Estados: A – 1, B – 2. Ahora, asignemos una tarea de tipo 3 al núcleo A -> cuesta 1 unidad. Estados: A – 3, B – 2. Ahora, asigne la tarea de tipo 2 en el núcleo B, donde ya se está realizando la tarea de tipo 2 -> unidad de costo 0. Estados: A – 3, B – 2. Por lo tanto, costo total = 1 + 1 + 0 + 1 + 1 = 4 unidades. Última tarea de tipo 1 asignada en cualquiera de los núcleos (digamos A) -> costo 1 unidad. Estados: A – 1, B – 2. Por lo tanto, costo total = 1 + 1 + 0 + 1 + 0 + 1 = 4 unidades.
Enfoque: dividir este problema en dos casos: el
primero es cuando el mismo tipo de tarea se está ejecutando actualmente en uno de los núcleos. Luego, simplemente asigne la próxima tarea a ese núcleo. Por ejemplo, en i = 3 (tercera tarea), cuando llega la tarea de tipo 1, podemos asignar esa tarea a ese núcleo donde anteriormente se estaba realizando la tarea de tipo 1. El costo de esto es 0 unidad.
El segundo caso es cuando el mismo tipo de tarea no se ejecuta en ninguno de los núcleos. Entonces, puede haber dos posibilidades. El subcaso 1 es, si hay al menos un núcleo libre, entonces asigne la próxima tarea a ese núcleo.
El subcaso 2 es que, si no hay un núcleo libre, entonces tenemos que dejar de procesar un tipo de tarea, liberar un núcleo y asignar la próxima tarea en ese núcleo de modo que el costo en el futuro sea mínimo. Para minimizar el costo, debemos detener un tipo de tarea que nunca volverá a ocurrir en el futuro. Si cada tarea en curso vuelve a ocurrir al menos una vez en el futuro, entonces debemos detener la tarea que volverá a ocurrir en último lugar entre todas las tareas en curso actualmente (es un enfoque codicioso y una tarea de voluntad).
Por ejemplo 2: en i = 4 (cuarta tarea), tarea tipo 3, tareas tipo 1 y tipo 2 actualmente en curso en dos núcleos, podemos detener la tarea tipo 1 o la tarea tipo 2 para iniciar la tarea tipo 3. Pero detendremos la tarea tipo 1 como tarea de tipo 1 vuelve a suceder después de la tarea de tipo dos.
C++
// C++ Program to find 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 same 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 that 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;
}
Java
// Java program to find out minimum
// cost to process m tasks
import java.util.*;
class GFG{
// Function to find out the farthest
// position where one of the currently
// ongoing tasks will rehappen.
static int find(int[] arr, int pos, int m,
boolean[] isRunning)
{
// Iterate form last to current
// position and find where the
// task will happen next.
int[] d = new int[m + 1];
for(int i = m - 1; 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 = Math.max(ele, maxipos);
return maxipos;
}
// Function to find out minimum cost to
// process all the tasks
static int mincost(int n, int m, 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).
@SuppressWarnings("unchecked")
Vector<Integer>[] freqarr = new Vector[m];
for(int i = 0; i < freqarr.length; i++)
freqarr[i] = new Vector<Integer>();
// 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.
int[] newvec = new int[m + 1];
for(int i = 0; i < m + 1; i++)
freqarr[m - 1].add(newvec[i]);
for(int i = m - 2; i > 0; i--)
{
Vector<Integer> nv = new Vector<>();
nv = freqarr[i + 1];
nv.insertElementAt(arr[i + 1] + 1,
arr[i + 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.
boolean[] isRunning = new boolean[m + 1];
// 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 same 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 that 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 = 0; j <= m; j++)
{
if (isRunning[j] && mini >
freqarr[i].get(j))
{
mini = freqarr[i].get(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 code
public static void main(String[] args)
{
// Test case 1
int n1 = 3;
int m1 = 6;
int[] arr1 = { 1, 2, 1, 3, 4, 1 };
System.out.print(mincost(n1, m1, arr1) + "\n");
// Test case 2
int n2 = 2;
int m2 = 6;
int[] arr2 = { 1, 2, 1, 3, 2, 1 };
System.out.print(mincost(n2, m2, arr2) + "\n");
// Test case 3
int n3 = 3;
int m3 = 31;
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 };
System.out.print(mincost(n3, m3 - 8, arr3) + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 Program to find 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 same 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 that 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
C#
// C# program to find out minimum
// cost to process m tasks
using System;
using System.Collections.Generic;
public class GFG{
// Function to find out the farthest
// position where one of the currently
// ongoing tasks will rehappen.
static int find(int[] arr, int pos, int m,
bool[] isRunning)
{
// Iterate form last to current
// position and find where the
// task will happen next.
int[] d = new int[m + 1];
for(int i = m - 1; 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;
foreach(int ele in d)
maxipos = Math.Max(ele, maxipos);
return maxipos;
}
// Function to find out minimum cost to
// process all the tasks
static int mincost(int n, int m, 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).
List<int>[] freqarr = new List<int>[m];
for(int i = 0; i < freqarr.Length; i++)
freqarr[i] = new List<int>();
// 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.
int[] newvec = new int[m + 1];
for(int i = 0; i < m + 1; i++)
freqarr[m - 1].Add(newvec[i]);
for(int i = m - 2; i > 0; i--)
{
List<int> nv = new List<int>();
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.
bool[] isRunning = new bool[m + 1];
// 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 same 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 that 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 = 0; 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 code
public static void Main(String[] args)
{
// Test case 1
int n1 = 3;
int m1 = 6;
int[] arr1 = { 1, 2, 1, 3, 4, 1 };
Console.Write(mincost(n1, m1, arr1) + "\n");
// Test case 2
int n2 = 2;
int m2 = 6;
int[] arr2 = { 1, 2, 1, 3, 2, 1 };
Console.Write(mincost(n2, m2, arr2) + "\n");
// Test case 3
int n3 = 3;
int m3 = 31;
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 };
Console.Write(mincost(n3, m3 - 8, arr3) + "\n");
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach
// Function to find out the farthest
// position where one of the currently
// ongoing tasks will rehappen.
function find(arr, pos, m, isRunning)
{
// Iterate form last to current
// position and find where the
// task will happen next.
let d = new Array(m + 1);
for(let i = m - 1; i > pos; i--)
{
if (isRunning[arr[i]])
d[arr[i]] = i;
}
// Find out maximum of all these
// positions and it is the
// farthest position.
let maxipos = 0;
for(let ele in d)
maxipos = Math.max(ele, maxipos);
return maxipos;
}
// Function to find out minimum cost to
// process all the tasks
function 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).
let freqarr = new Array(m);
for(let i = 0; i < freqarr.length; i++)
freqarr[i] = new Array();
// 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.
let newvec = new Array(m+1);
for(let i = 0; i < m + 1; i++)
freqarr[m - 1].push(newvec[i]);
for(let i = m - 2; i > 0; i--)
{
let nv = new Array();
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.
let isRunning = new Array(m+1);
// cost denotes total cost to assign tasks
let cost = 0;
// truecount denotes number of occupied cores
let truecount = 0;
// Iterate through each task and find the
// total cost.
for(let i = 0; i < m; i++)
{
// ele denotes type of task.
let ele = arr[i];
// Case 1: if same 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 that 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
let mini = 100000;
// Set index of minimum frequency task to 0.
let miniind = 0;
// Find the minimum frequency task
// type(miniind) and frequency(mini).
for(let j = 0; 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
let farpos = find(arr, i, m,
isRunning);
isRunning[arr[farpos]] = false;
isRunning[ele] = true;
cost += 1;
}
}
}
}
// Return total cost
return cost;
}
// Driver Code
// Test case 1
let n1 = 3;
let m1 = 6;
let arr1 = [ 1, 2, 1, 3, 4, 1 ];
document.write(mincost(n1, m1, arr1) + "<br>");
// Test case 2
let n2 = 2;
let m2 = 6;
let arr2 = [ 1, 2, 1, 3, 2, 1 ];
document.write(mincost(n2, m2, arr2) + "<br>");
// Test case 3
let n3 = 3;
let m3 = 31;
let 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];
document.write(mincost(n3, m3+8, arr3) + 1 + "<br>");
// This code is contributed by code_hunt.
</script>
Producción:
4 4 18
Complejidad de tiempo: O (m ^ 2)
Complejidad de espacio: O (m ^ 2), (para almacenar el freqarr)