Dada una serie de trabajos donde cada trabajo tiene una fecha límite y una ganancia asociada (si el trabajo se termina antes de la fecha límite). También se da que cada trabajo requiere una sola unidad de tiempo, por lo que la fecha límite mínima posible para cualquier trabajo es 1. Cómo maximizar la ganancia total si solo se puede programar un trabajo a la vez.
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
A continuación se muestra el algoritmo paso a paso para resolver el problema usando TreeSet en Java:
- Ordena todos los trabajos según sus respectivas ganancias en orden decreciente.
- Cree un TreeSet e inserte todos los enteros de 0 a n-1.
- Atraviesa la array de trabajos y para i -ésimo trabajo
- Busque un intervalo de tiempo ‘x’ en el TreeSet con un valor máximo que sea menor que la fecha límite del i -ésimo trabajo.
- Si existe algún valor, incluya ese trabajo en la respuesta y elimine ‘x’ del TreeSet
- De lo contrario, verifique los trabajos restantes.
A continuación se muestra la implementación del algoritmo anterior:
import java.io.*;
import java.util.*;
public class Solution {
// Job class
public static class Job {
char id;
int deadline;
int profit;
// Constructor
Job(char id, int deadline, int profit)
{
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
}
public static class Sorted implements Comparator {
// Function to implement comparator
public int compare(Object o1, Object o2)
{
Job j1 = (Job)o1;
Job j2 = (Job)o2;
if (j1.profit != j2.profit)
return j2.profit - j1.profit;
else
return j2.deadline - j1.deadline;
}
}
// Function to print job scheduling
public static void printJobScheduling(Job jobs[], int n)
{
// Creating object of Sorted class
Sorted sorter = new Sorted();
Arrays.sort(jobs, sorter);
// Creating TreeSet Object
TreeSet<Integer> ts = new TreeSet<>();
for (int i = 0; i < n; i++)
ts.add(i);
for (int i = 0; i < n; i++) {
Integer x = ts.floor(jobs[i].deadline - 1);
if (x != null) {
System.out.print(jobs[i].id + " ");
ts.remove(x);
}
}
}
// Driver Code
public static void main(String[] args)
{
int n = 5;
Job[] jobs = new Job[n];
jobs[0] = new Job('a', 2, 100);
jobs[1] = new Job('b', 1, 19);
jobs[2] = new Job('c', 2, 27);
jobs[3] = new Job('d', 1, 25);
jobs[4] = new Job('e', 3, 15);
printJobScheduling(jobs, n);
}
// Contributed by Dipesh Jain (dipesh_jain)
}
Complejidad de tiempo : O(N*log(N))
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por dipesh_jain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA