Dado un conjunto de n trabajos donde cada trabajo i tiene una fecha límite di >=1 y una ganancia pi>=0. Solo se puede programar un trabajo a la vez. Cada trabajo tarda 1 unidad de tiempo en completarse. Obtenemos la ganancia si y solo si el trabajo se completa antes de su fecha límite. La tarea es encontrar el subconjunto de puestos de trabajo que maximiza las ganancias.
Ejemplos:
Input: Four Jobs with following deadlines and profits
JobID Deadline Profit
a 4 20
b 1 10
c 1 40
d 1 30
Output: Following is maximum profit sequence of jobs:
c, a
Input: Five Jobs with following deadlines and profits
JobID Deadline Profit
a 2 100
b 1 19
c 2 27
d 1 25
e 3 15
Output: Following is maximum profit sequence of jobs:
c, a, e
Una solución codiciosa de la complejidad del tiempo O(n 2 ) ya se discute aquí . A continuación se muestra el algoritmo codicioso simple.
- Ordene todos los trabajos en orden decreciente de ganancias.
- Inicialice la secuencia de resultados como primer trabajo en trabajos ordenados.
- Haga lo siguiente para los trabajos n-1 restantes
- Si el trabajo actual puede caber en la secuencia de resultados actual sin perder la fecha límite, agregue el trabajo actual al resultado. De lo contrario, ignore el trabajo actual.
La operación costosa en la solución Greedy es asignar un espacio libre para un trabajo. Estábamos recorriendo todos y cada uno de los intervalos para un trabajo y asignando el mayor intervalo de tiempo posible (<fecha límite) que estaba disponible.
¿Qué significa mayor franja horaria?
Supongamos que un trabajo J1 tiene una fecha límite de tiempo t = 5. Asignamos el intervalo de tiempo más grande que está libre y menor que la fecha límite, es decir, 4-5 para este trabajo. Ahora entra otro trabajo J2 con una fecha límite de 5, por lo que el intervalo de tiempo asignado será 3-4 dado que ya se ha asignado 4-5 al trabajo J1.
¿Por qué asignar la mayor franja horaria (libre) a un trabajo?
Ahora asignamos la franja de tiempo más grande posible ya que si asignamos una franja de tiempo incluso menor que la disponible, es posible que haya algún otro trabajo que no cumpla con su fecha límite.
Ejemplo:
J1 con fecha límite d1 = 5, ganancia 40
J2 con fecha límite d2 = 1, ganancia 20
Supongamos que para el trabajo J1 asignamos un intervalo de tiempo de 0-1. Ahora el trabajo J2 no se puede realizar ya que realizaremos el trabajo J1 durante ese intervalo de tiempo.
Uso de conjuntos disjuntos para la secuenciación de trabajos
Todos los intervalos de tiempo son inicialmente conjuntos individuales. Primero encontramos la fecha límite máxima de todos los trabajos. Sea el plazo máximo m. Creamos m+1 conjuntos individuales. Si a un trabajo se le asigna un intervalo de tiempo de t donde t >= 0, entonces el trabajo se programa durante [t-1, t]. Entonces, un conjunto con valor X representa el intervalo de tiempo [X-1, X].
Necesitamos realizar un seguimiento de la mayor franja de tiempo disponible que se puede asignar a un trabajo determinado que tiene una fecha límite. Usamos la array principal de estructuras de datos de conjuntos disjuntos para este propósito. La raíz del árbol es siempre el último espacio disponible. Si para una fecha límite d no hay ningún espacio disponible, entonces la raíz sería 0. A continuación se detallan los pasos.
Inicializar conjunto disjunto: crea conjuntos disjuntos iniciales.
// m is maximum deadline of a job
parent = new int[m + 1];
// Every node is a parent of itself
for (int i = 0; i ≤ m; i++)
parent[i] = i;
Buscar: busca la última franja horaria disponible.
// Returns the maximum available time slot
find(s)
{
// Base case
if (s == parent[s])
return s;
// Recursive call with path compression
return parent[s] = find(parent[s]);
}
Unión :
Merges two sets.
// Makes u as parent of v.
union(u, v)
{
// update the greatest available
// free slot to u
parent[v] = u;
}
¿Cómo es que find devuelve el último intervalo de tiempo disponible?
Inicialmente, todos los intervalos de tiempo son intervalos individuales. Entonces, el intervalo de tiempo devuelto siempre es máximo. Cuando asignamos un intervalo de tiempo ‘t’ a un trabajo, hacemos la unión de ‘t’ con ‘t-1’ de manera que ‘t-1’ se convierte en padre de ‘t’. Para ello llamamos union(t-1, t). Esto significa que todas las consultas futuras para el intervalo de tiempo t ahora devolverán el último intervalo de tiempo disponible para el conjunto representado por t-1.
Implementación:
La siguiente es la implementación del algoritmo anterior.
C++
// C++ Program to find the maximum profit job sequence
// from a given array of jobs with deadlines and profits
#include<bits/stdc++.h>
using namespace std;
// A structure to represent various attributes of a Job
struct Job
{
// Each job has id, deadline and profit
char id;
int deadLine, profit;
};
// A Simple Disjoint Set Data Structure
struct DisjointSet
{
int *parent;
// Constructor
DisjointSet(int n)
{
parent = new int[n+1];
// Every node is a parent of itself
for (int i = 0; i <= n; i++)
parent[i] = i;
}
// Path Compression
int find(int s)
{
/* Make the parent of the nodes in the path
from u--> parent[u] point to parent[u] */
if (s == parent[s])
return s;
return parent[s] = find(parent[s]);
}
// Makes u as parent of v.
void merge(int u, int v)
{
//update the greatest available
//free slot to u
parent[v] = u;
}
};
// Used to sort in descending order on the basis
// of profit for each job
bool cmp(Job a, Job b)
{
return (a.profit > b.profit);
}
// Functions returns the maximum deadline from the set
// of jobs
int findMaxDeadline(struct Job arr[], int n)
{
int ans = INT_MIN;
for (int i = 0; i < n; i++)
ans = max(ans, arr[i].deadLine);
return ans;
}
int printJobScheduling(Job arr[], int n)
{
// Sort Jobs in descending order on the basis
// of their profit
sort(arr, arr + n, cmp);
// Find the maximum deadline among all jobs and
// create a disjoint set data structure with
// maxDeadline disjoint sets initially.
int maxDeadline = findMaxDeadline(arr, n);
DisjointSet ds(maxDeadline);
// Traverse through all the jobs
for (int i = 0; i < n; i++)
{
// Find the maximum available free slot for
// this job (corresponding to its deadline)
int availableSlot = ds.find(arr[i].deadLine);
// If maximum available free slot is greater
// than 0, then free slot available
if (availableSlot > 0)
{
// This slot is taken by this job 'i'
// so we need to update the greatest
// free slot. Note that, in merge, we
// make first parameter as parent of
// second parameter. So future queries
// for availableSlot will return maximum
// available slot in set of
// "availableSlot - 1"
ds.merge(ds.find(availableSlot - 1),
availableSlot);
cout << arr[i].id << " ";
}
}
}
// Driver code
int main()
{
Job arr[] = { { 'a', 2, 100 }, { 'b', 1, 19 },
{ 'c', 2, 27 }, { 'd', 1, 25 },
{ 'e', 3, 15 } };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Following jobs need to be "
<< "executed for maximum profit\n";
printJobScheduling(arr, n);
return 0;
}
Java
// Java program to find the maximum profit job sequence
// from a given array of jobs with deadlines and profits
import java.util.*;
// A Simple Disjoint Set Data Structure
class DisjointSet
{
int parent[];
// Constructor
DisjointSet(int n)
{
parent = new int[n + 1];
// Every node is a parent of itself
for (int i = 0; i <= n; i++)
parent[i] = i;
}
// Path Compression
int find(int s)
{
/* Make the parent of the nodes in the path
from u--> parent[u] point to parent[u] */
if (s == parent[s])
return s;
return parent[s] = find(parent[s]);
}
// Makes u as parent of v.
void merge(int u, int v)
{
//update the greatest available
//free slot to u
parent[v] = u;
}
}
class Job implements Comparator<Job>
{
// Each job has a unique-id, profit and deadline
char id;
int deadline, profit;
// Constructors
public Job() { }
public Job(char id,int deadline,int profit)
{
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
// Returns the maximum deadline from the set of jobs
public static int findMaxDeadline(ArrayList<Job> arr)
{
int ans = Integer.MIN_VALUE;
for (Job temp : arr)
ans = Math.max(temp.deadline, ans);
return ans;
}
// Prints optimal job sequence
public static void printJobScheduling(ArrayList<Job> arr)
{
// Sort Jobs in descending order on the basis
// of their profit
Collections.sort(arr, new Job());
// Find the maximum deadline among all jobs and
// create a disjoint set data structure with
// maxDeadline disjoint sets initially.
int maxDeadline = findMaxDeadline(arr);
DisjointSet dsu = new DisjointSet(maxDeadline);
// Traverse through all the jobs
for (Job temp : arr)
{
// Find the maximum available free slot for
// this job (corresponding to its deadline)
int availableSlot = dsu.find(temp.deadline);
// If maximum available free slot is greater
// than 0, then free slot available
if (availableSlot > 0)
{
// This slot is taken by this job 'i'
// so we need to update the greatest free
// slot. Note that, in merge, we make
// first parameter as parent of second
// parameter. So future queries for
// availableSlot will return maximum slot
// from set of "availableSlot - 1"
dsu.merge(dsu.find(availableSlot - 1),
availableSlot);
System.out.print(temp.id + " ");
}
}
System.out.println();
}
// Used to sort in descending order on the basis
// of profit for each job
public int compare(Job j1, Job j2)
{
return j1.profit > j2.profit? -1: 1;
}
}
// Driver code
class Main
{
public static void main(String args[])
{
ArrayList<Job> arr=new ArrayList<Job>();
arr.add(new Job('a',2,100));
arr.add(new Job('b',1,19));
arr.add(new Job('c',2,27));
arr.add(new Job('d',1,25));
arr.add(new Job('e',3,15));
System.out.println("Following jobs need to be "+
"executed for maximum profit");
Job.printJobScheduling(arr);
}
}
C#
// C# program to find the maximum profit job sequence
// from a given array of jobs with deadlines and profits
using System;
using System.Collections.Generic;
// A Simple Disjoint Set Data Structure
public class DisjointSet
{
public int[] parent;
// Constructor
public DisjointSet(int n)
{
parent = new int[n + 1];
// Every node is a parent of itself
for (int i = 0; i <= n; i++)
parent[i] = i;
}
// Path Compression
public int find(int s)
{
/* Make the parent of the nodes in the path
from u--> parent[u] point to parent[u] */
if (s == parent[s])
return s;
return parent[s] = find(parent[s]);
}
// Makes u as parent of v.
public void merge(int u, int v)
{
//update the greatest available
//free slot to u
parent[v] = u;
}
}
public class Job:Comparer<Job>
{
// Each job has a unique-id, profit and deadline
public char id;
public int deadline, profit;
// Constructors
public Job() { }
public Job(char id,int deadline,int profit)
{
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
// Returns the maximum deadline from the set of jobs
public static int findMaxDeadline(List<Job> arr)
{
int ans = Int32.MinValue;
for (int i=0;i<arr.Count;i++){
Job temp = arr[i];
ans = Math.Max(temp.deadline, ans);
}
return ans;
}
// Prints optimal job sequence
public static void printJobScheduling(List<Job> arr)
{
// Sort Jobs in descending order on the basis
// of their profit
//Collections.sort(arr, new Job());
arr.Sort(new Job());
// Find the maximum deadline among all jobs and
// create a disjoint set data structure with
// maxDeadline disjoint sets initially.
int maxDeadline = findMaxDeadline(arr);
DisjointSet dsu = new DisjointSet(maxDeadline);
// Traverse through all the jobs
for (int i=0;i<arr.Count;i++)
{
Job temp = arr[i];
// Find the maximum available free slot for
// this job (corresponding to its deadline)
int availableSlot = dsu.find(temp.deadline);
// If maximum available free slot is greater
// than 0, then free slot available
if (availableSlot > 0)
{
// This slot is taken by this job 'i'
// so we need to update the greatest free
// slot. Note that, in merge, we make
// first parameter as parent of second
// parameter. So future queries for
// availableSlot will return maximum slot
// from set of "availableSlot - 1"
dsu.merge(dsu.find(availableSlot - 1),availableSlot);
Console.Write(temp.id + " ");
}
}
Console.Write("\n");
}
// Used to sort in descending order on the basis
// of profit for each job
public override int Compare(Job j1, Job j2)
{
return j1.profit > j2.profit? -1: 1;
}
}
public class GFG{
static public void Main (){
//Code
List<Job> arr=new List<Job>();
arr.Add(new Job('a',2,100));
arr.Add(new Job('b',1,19));
arr.Add(new Job('c',2,27));
arr.Add(new Job('d',1,25));
arr.Add(new Job('e',3,15));
Console.Write("Following jobs need to be executed for maximum profit");
Console.Write("\n");
Job.printJobScheduling(arr);
}
}
// This code is contributed by shruti456rawal
Python3
# Python3 program to find the maximum profit
# job sequence from a given array of jobs
# with deadlines and profits
import sys
class DisjointSet:
def __init__(self, n):
self.parent = [i for i in range(n + 1)]
def find(self, s):
# Make the parent of nodes in the path from
# u --> parent[u] point to parent[u]
if s == self.parent[s]:
return s
self.parent[s] = self.find(self.parent[s])
return self.parent[s]
# Make us as parent of v
def merge(self, u, v):
# Update the greatest available
# free slot to u
self.parent[v] = u
def cmp(a):
return a['profit']
def findmaxdeadline(arr, n):
"""
:param arr: Job array
:param n: length of array
:return: maximum deadline from the set of jobs
"""
ans = - sys.maxsize - 1
for i in range(n):
ans = max(ans, arr[i]['deadline'])
return ans
def printjobscheduling(arr, n):
# Sort jobs in descending order on
# basis of their profit
arr = sorted(arr, key = cmp, reverse = True)
"""
Find the maximum deadline among all jobs and
create a disjoint set data structure with
max_deadline disjoint sets initially
"""
max_deadline = findmaxdeadline(arr, n)
ds = DisjointSet(max_deadline)
for i in range(n):
# find maximum available free slot for
# this job (corresponding to its deadline)
available_slot = ds.find(arr[i]['deadline'])
if available_slot > 0:
# This slot is taken by this job 'i'
# so we need to update the greatest free slot.
# Note: In merge, we make first parameter
# as parent of second parameter.
# So future queries for available_slot will
# return maximum available slot in set of
# "available_slot - 1"
ds.merge(ds.find(available_slot - 1),
available_slot)
print(arr[i]['id'], end = " ")
# Driver Code
if __name__ == "__main__":
arr = [{'id': 'a', 'deadline': 2, 'profit': 100},
{'id': 'b', 'deadline': 1, 'profit': 19},
{'id': 'c', 'deadline': 2, 'profit': 27},
{'id': 'd', 'deadline': 1, 'profit': 25},
{'id': 'e', 'deadline': 3, 'profit': 15}]
n = len(arr)
print("Following jobs need to be",
"executed for maximum profit")
printjobscheduling(arr, n)
# This code is contributed by Rajat Srivastava
Following jobs need to be executed for maximum profit a c e
Este artículo es una contribución de Chirag Agarwal. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA