Programación de tareas prioritarias en tiempo limitado y minimización de pérdidas

Dadas n tareas con hora de llegada, prioridad y número de unidades de tiempo que necesitan. Necesitamos programar estas tareas en un solo recurso. El objetivo es organizar las tareas de manera que se tomen las tareas de máxima prioridad. El objetivo es minimizar la suma del producto de la prioridad y el tiempo restante de las tareas que no están programadas debido al tiempo limitado. Este criterio simplemente significa que la programación debe causar la mínima pérdida posible. Ejemplos:

Input : Total time = 3
        Task1: arrival = 1, units = 2, priority = 300
        Task2: arrival = 2, units = 2, priority = 100
Output : 100
Explanation : Two tasks are given and time to finish 
them is 3 units. First task arrives at time 1 and it
needs 2 units. Since no other task is running at that
time, we take it. 1 unit of task 1 is over. Now task 2 
arrives. The priority of task 1 is more than task 2 
(300 > 100) thus 1 more unit  of task 1 is employed. 
Now 1 unit of time is left and we have 2 units of task
2 to be done. So simply 1 unit of task 2 is done and 
the answer is ( units of task 2 left X priority of 
task 2 ) = 1 X 100 = 100

Input : Total Time = 3
        Task1: arrival = 1, units = 1, priority = 100
        Task2: arrival = 2, units = 2, priority = 300
Output : 0

Usamos una cola de prioridad y programamos una unidad de tarea a la vez.

1. Inicialice la pérdida total como la suma de cada prioridad y unidades. La idea es inicializar el resultado como máximo, luego restar una a una las prioridades de las tareas que están programadas.
2. Ordenar todas las tareas según la hora de llegada.
3. Procese a través de cada unidad de tiempo desde 1 hasta el tiempo total. Para la hora actual, elija la tarea de mayor prioridad que esté disponible. Programe 1 unidad de esta tarea y reste su prioridad de la pérdida total.

A continuación se muestra la implementación en C++ de los pasos anteriores. 

// C++ code for task scheduling on basis
// of priority and arrival time
#include "bits/stdc++.h"
using namespace std;
 
// t is total time. n is number of tasks.
// arriv[] stores arrival times. units[]
// stores units of time required. prior[]
// stores priorities.
int minLoss(int n, int t, int arriv[],
   int units[], int prior[])
{
 // Calculating maximum possible answer
 // that could be calculated. Later we
 // will subtract the tasks from it
 // accordingly.
 int ans = 0;
 for (int i = 0; i < n; i++)
  ans += prior[i] * units[i];
 
 // Pushing tasks in a vector so that they
 // could be sorted according with their
 // arrival time
 vector<pair<int, int> > v;
 for (int i = 0; i < n; i++)
  v.push_back({ arriv[i], i });
 
 // Sorting tasks in vector identified by
 // index and arrival time with respect
 // to their arrival time
 sort(v.begin(), v.end());
 
 // Priority queue to hold tasks to be
 // scheduled.
 priority_queue<pair<int, int> > pq;
 
 // Consider one unit of time at a time.
 int ptr = 0; // index in sorted vector
 for (int i = 1; i <= t; i++) {
 
  // Push all tasks that have arrived at
  // this time. Note that the tasks that
  // arrived earlier and could not be scheduled
  // are already in pq.
  while (ptr < n and v[ptr].x == i) {
   pq.push({ prior[v[ptr].y], units[v[ptr].y] });
   ptr++;
  }
 
  // Remove top priority task to be scheduled
  // at time i.
  if (!pq.empty()) {
   auto tmp = pq.top();
   pq.pop();
 
   // Removing 1 unit of task
   // from answer as we could
   // schedule it.
   ans -= tmp.x;
   tmp.y--;
   if (tmp.y)
    pq.push(tmp);
  }
 }
 
 return ans;
}
 
// driver code
int main()
{
 int n = 2, t = 3;
 int arriv[] = { 1, 2 };
 int units[] = { 2, 2 };
 int prior[] = { 100, 300 };
 
 printf("%d\n", minLoss(n, t, arriv, units, prior));
 return 0;
}

Producción:

100

Complejidad de Tiempo: O(nlogn), usado para ordenar el arreglo
Espacio Auxiliar: O(n), como espacio extra de tamaño n, se usa para hacer un vector de pares.
Este artículo es una contribución de Parth Trehan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.