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
Una solución simple es generar todos los subconjuntos de un conjunto dado de trabajos y verificar subconjuntos individuales para determinar la viabilidad de los trabajos en ese subconjunto. Realice un seguimiento de la ganancia máxima entre todos los subconjuntos factibles. La complejidad temporal de esta solución es exponencial.
Este es un problema de algoritmo codicioso estándar.
El siguiente es el algoritmo.
1) Ordenar todos los trabajos en orden decreciente de ganancias.
2) Iterar en los trabajos en orden decreciente de ganancias. Para cada trabajo, haga lo siguiente:
a) Encuentre un intervalo de tiempo i, tal que el intervalo esté vacío e i <fecha límite e i sea mayor. Coloque el trabajo en
este intervalo y márquelo ranura llena.
b) Si no existe tal i, entonces ignore el trabajo.
La siguiente es la implementación del algoritmo anterior.
C++
// Program to find the maximum profit job sequence from a
// given array of jobs with deadlines and profits
#include <algorithm>
#include <iostream>
using namespace std;
// A structure to represent a job
struct Job {
char id; // Job Id
int dead; // Deadline of job
int profit; // Profit if job is over before or on
// deadline
};
// This function is used for sorting all jobs according to
// profit
bool comparison(Job a, Job b)
{
return (a.profit > b.profit);
}
// Returns minimum number of platforms required
void printJobScheduling(Job arr[], int n)
{
// Sort all jobs according to decreasing order of profit
sort(arr, arr + n, comparison);
int result[n]; // To store result (Sequence of jobs)
bool slot[n]; // To keep track of free time slots
// Initialize all slots to be free
for (int i = 0; i < n; i++)
slot[i] = false;
// Iterate through all given jobs
for (int i = 0; i < n; i++) {
// Find a free slot for this job (Note that we start
// from the last possible slot)
for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {
// Free slot found
if (slot[j] == false) {
result[j] = i; // Add this job to result
slot[j] = true; // Make this slot occupied
break;
}
}
}
// Print the result
for (int i = 0; i < n; i++)
if (slot[i])
cout << arr[result[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 is maximum profit sequence of jobs "
"\n";
// Function call
printJobScheduling(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// A structure to represent a job
typedef struct Job {
char id; // Job Id
int dead; // Deadline of job
int profit; // Profit if job is over before or on deadline
} Job;
// This function is used for sorting all jobs according to
// profit
int compare(const void* a, const void* b)
{
Job* temp1 = (Job*)a;
Job* temp2 = (Job*)b;
return (temp2->profit - temp1->profit);
}
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
// Returns minimum number of platforms required
void printJobScheduling(Job arr[], int n)
{
// Sort all jobs according to decreasing order of profit
qsort(arr, n, sizeof(Job), compare);
// sort(arr, arr+n, comparison);
int result[n]; // To store result (Sequence of jobs)
bool slot[n]; // To keep track of free time slots
// Initialize all slots to be free
for (int i = 0; i < n; i++)
slot[i] = false;
// Iterate through all given jobs
for (int i = 0; i < n; i++) {
// Find a free slot for this job (Note that we start
// from the last possible slot)
for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {
// Free slot found
if (slot[j] == false) {
result[j] = i; // Add this job to result
slot[j] = true; // Make this slot occupied
break;
}
}
}
// Print the result
for (int i = 0; i < n; i++)
if (slot[i])
printf("%c ", arr[result[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]);
printf(
"Following is maximum profit sequence of jobs \n");
// Function call
printJobScheduling(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Program to find the maximum profit
// job sequence from a given array
// of jobs with deadlines and profits
import java.util.*;
class 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;
}
// Function to schedule the jobs take 2 arguments
// arraylist and no of jobs to schedule
void printJobScheduling(ArrayList<Job> arr, int t)
{
// Length of array
int n = arr.size();
// Sort all jobs according to decreasing order of
// profit
Collections.sort(arr,(a, b) -> b.profit - a.profit);
// To keep track of free time slots
boolean result[] = new boolean[t];
// To store result (Sequence of jobs)
char job[] = new char[t];
// Iterate through all given jobs
for (int i = 0; i < n; i++) {
// Find a free slot for this job (Note that we
// start from the last possible slot)
for (int j = Math.min(t - 1, arr.get(i).deadline - 1); j >= 0; j--) {
// Free slot found
if (result[j] == false) {
result[j] = true;
job[j] = arr.get(i).id;
break;
}
}
}
// Print the sequence
for (char jb : job)
System.out.print(jb + " ");
System.out.println();
}
// Driver code
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));
// Function call
System.out.println(
"Following is maximum profit sequence of jobs");
Job job = new Job();
// Calling function
job.printJobScheduling(arr, 3);
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Program to find the maximum profit
# job sequence from a given array
# of jobs with deadlines and profits
# function to schedule the jobs take 2
# arguments array and no of jobs to schedule
def printJobScheduling(arr, t):
# length of array
n = len(arr)
# Sort all jobs according to
# decreasing order of profit
for i in range(n):
for j in range(n - 1 - i):
if arr[j][2] < arr[j + 1][2]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# To keep track of free time slots
result = [False] * t
# To store result (Sequence of jobs)
job = ['-1'] * t
# Iterate through all given jobs
for i in range(len(arr)):
# Find a free slot for this job
# (Note that we start from the
# last possible slot)
for j in range(min(t - 1, arr[i][1] - 1), -1, -1):
# Free slot found
if result[j] is False:
result[j] = True
job[j] = arr[i][0]
break
# print the sequence
print(job)
# Driver COde
arr = [['a', 2, 100], # Job Array
['b', 1, 19],
['c', 2, 27],
['d', 1, 25],
['e', 3, 15]]
print("Following is maximum profit sequence of jobs")
# Function Call
printJobScheduling(arr, 3)
# This code is contributed
# by Anubhav Raj Singh
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;
class GFG : IComparer<Job>
{
public int Compare(Job x, Job y)
{
if (x.profit == 0 || y.profit== 0)
{
return 0;
}
// CompareTo() method
return (y.profit).CompareTo(x.profit);
}
}
public class Job{
// Each job has a unique-id,
// profit and deadline
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;
}
// Function to schedule the jobs take 2
// arguments arraylist and no of jobs to schedule
void printJobScheduling(List<Job> arr, int t)
{
// Length of array
int n = arr.Count;
GFG gg = new GFG();
// Sort all jobs according to
// decreasing order of profit
arr.Sort(gg);
// To keep track of free time slots
bool[] result = new bool[t];
// To store result (Sequence of jobs)
char[] job = new char[t];
// Iterate through all given jobs
for (int i = 0; i < n; i++)
{
// Find a free slot for this job
// (Note that we start from the
// last possible slot)
for (int j
= Math.Min(t - 1, arr[i].deadline - 1);
j >= 0; j--) {
// Free slot found
if (result[j] == false)
{
result[j] = true;
job[j] = arr[i].id;
break;
}
}
}
// Print the sequence
foreach (char jb in job)
{
Console.Write(jb + " ");
}
Console.WriteLine();
}
// Driver code
static public void Main ()
{
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));
// Function call
Console.WriteLine("Following is maximum "
+ "profit sequence of jobs");
Job job = new Job();
// Calling function
job.printJobScheduling(arr, 3);
}
}
// This code is contributed by avanitracchadiya2155.
Javascript
<script>
// Program to find the maximum profit
// job sequence from a given array
// of jobs with deadlines and profits
// function to schedule the jobs take 2
// arguments array and no of jobs to schedule
function printJobScheduling(arr, t){
// length of array
let n = arr.length;
// Sort all jobs according to
// decreasing order of profit
for(let i=0;i<n;i++){
for(let j = 0;j<(n - 1 - i);j++){
if(arr[j][2] < arr[j + 1][2]){
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
// To keep track of free time slots
let result = [];
// To store result (Sequence of jobs)
let job = [];
for(let i = 0;i<t;i++){
job[i] = '-1';
result[i] = false;
}
// Iterate through all given jobs
for(let i= 0;i<arr.length;i++){
// Find a free slot for this job
// (Note that we start from the
// last possible slot)
for(let j = (t - 1, arr[i][1] - 1);j>=0;j--){
// Free slot found
if(result[j] == false){
result[j] = true;
job[j] = arr[i][0];
break;
}
}
}
// print the sequence
document.write(job);
}
// Driver COde
arr = [['a', 2, 100], // Job Array
['b', 1, 19],
['c', 2, 27],
['d', 1, 25],
['e', 3, 15]];
document.write("Following is maximum profit sequence of jobs ");
document.write("<br>");
// Function Call
printJobScheduling(arr, 3) ;
</script>
Producción
Following is maximum profit sequence of jobs c a e
La complejidad temporal de la solución anterior es O(n 2 ). Se puede optimizar usando Priority Queue(max heap) .
El algoritmo es el siguiente:
- Ordenar los trabajos en función de sus plazos.
- Iterar desde el final y calcular los espacios disponibles entre cada dos plazos consecutivos. Incluya la ganancia, la fecha límite y la identificación del trabajo del i-ésimo trabajo en el montón máximo.
- Mientras las ranuras estén disponibles y queden trabajos en el montón máximo, incluya la identificación del trabajo con la ganancia máxima y la fecha límite en el resultado.
- Ordene la array de resultados en función de sus fechas límite.
Aquí está la implementación del algoritmo anterior.
C++
#include <bits/stdc++.h>
using namespace std;
// A structure to represent a job
struct Job {
char id; // Job Id
int dead; // Deadline of job
int profit; // Profit earned if job is completed before
// deadline
};
// Custom sorting helper struct which is used for sorting
// all jobs according to profit
struct jobProfit {
bool operator()(Job const& a, Job const& b)
{
return (a.profit < b.profit);
}
};
// Returns minimum number of platforms required
void printJobScheduling(Job arr[], int n)
{
vector<Job> result;
sort(arr, arr + n,
[](Job a, Job b) { return a.dead < b.dead; });
// set a custom priority queue
priority_queue<Job, vector<Job>, jobProfit> pq;
for (int i = n - 1; i >= 0; i--) {
int slot_available;
// we count the slots available between two jobs
if (i == 0) {
slot_available = arr[i].dead;
}
else {
slot_available = arr[i].dead - arr[i - 1].dead;
}
// include the profit of job(as priority),
// deadline and job_id in maxHeap
pq.push(arr[i]);
while (slot_available > 0 && pq.size() > 0) {
// get the job with the most profit
Job job = pq.top();
pq.pop();
// reduce the slots
slot_available--;
// add it to the answer
result.push_back(job);
}
}
// sort the result based on the deadline
sort(result.begin(), result.end(),
[&](Job a, Job b) { return a.dead < b.dead; });
// print the result
for (int i = 0; i < result.size(); i++)
cout << result[i].id << ' ';
cout << endl;
}
int main()
{
// Driver code
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 is maximum profit sequence of jobs "
"\n";
// Function call
printJobScheduling(arr, n);
return 0;
}
// This code is contributed By Reetu Raj Dubey
Java
// Java implementation of above approach
// Program to find the maximum profit
// job sequence from a given array
// of jobs with deadlines and profits
import java.util.*;
class GFG {
// a class to represent job
static class Job {
char job_id;
int deadline;
int profit;
Job(char job_id, int deadline, int profit)
{
this.deadline = deadline;
this.job_id = job_id;
this.profit = profit;
}
}
static void printJobScheduling(ArrayList<Job> arr)
{
int n = arr.size();
// sorting the array on the
// basis of their deadlines
Collections.sort(arr, (a, b) -> {
return a.deadline - b.deadline;
});
// initialise the result array and maxHeap
ArrayList<Job> result = new ArrayList<>();
PriorityQueue<Job> maxHeap = new PriorityQueue<>(
(a, b) -> { return b.profit - a.profit; });
// starting the iteration from the end
for (int i = n - 1; i > -1; i--) {
int slot_available;
// calculate slots between two deadlines
if (i == 0) {
slot_available = arr.get(i).deadline;
}
else {
slot_available = arr.get(i).deadline
- arr.get(i - 1).deadline;
}
// include the profit of job(as priority),
// deadline and job_id in maxHeap
maxHeap.add(arr.get(i));
while (slot_available > 0
&& maxHeap.size() > 0) {
// get the job with max_profit
Job job = maxHeap.remove();
// reduce the slots
slot_available--;
// include the job in the result array
result.add(job);
}
}
// jobs included might be shuffled
// sort the result array by their deadlines
Collections.sort(result, (a, b) -> {
return a.deadline - b.deadline;
});
for (Job job : result) {
System.out.print(job.job_id + " ");
}
System.out.println();
}
// Driver Code
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));
// Function call
System.out.println("Following is maximum "
+ "profit sequence of jobs");
// Calling function
printJobScheduling(arr);
}
}
// This code is contributed by Karandeep Singh
Python3
# Program to find the maximum profit
# job sequence from a given array
# of jobs with deadlines and profits
import heapq
def printJobScheduling(arr):
n = len(arr)
# arr[i][0] = job_id, arr[i][1] = deadline, arr[i][2] = profit
# sorting the array on the
# basis of their deadlines
arr.sort(key=lambda x: x[1])
# initialise the result array and maxHeap
result = []
maxHeap = []
# starting the iteration from the end
for i in range(n - 1, -1, -1):
# calculate slots between two deadlines
if i == 0:
slots_available = arr[i][1]
else:
slots_available = arr[i][1] - arr[i - 1][1]
# include the profit of job(as priority), deadline
# and job_id in maxHeap
# note we push negative value in maxHeap to convert
# min heap to max heap in python
heapq.heappush(maxHeap, (-arr[i][2], arr[i][1], arr[i][0]))
while slots_available and maxHeap:
# get the job with max_profit
profit, deadline, job_id = heapq.heappop(maxHeap)
# reduce the slots
slots_available -= 1
# include the job in the result array
result.append([job_id, deadline])
# jobs included might be shuffled
# sort the result array by their deadlines
result.sort(key=lambda x: x[1])
for job in result:
print(job[0], end=" ")
print()
# Driver COde
arr = [['a', 2, 100], # Job Array
['b', 1, 19],
['c', 2, 27],
['d', 1, 25],
['e', 3, 15]]
print("Following is maximum profit sequence of jobs")
# Function Call
printJobScheduling(arr)
# This code is contributed
# by Shivam Bhagat
Producción
Following is maximum profit sequence of jobs a c e
Complejidad del tiempo : O(nlog(n))
Complejidad espacial : O(n)
También se puede optimizar utilizando la estructura de datos de conjuntos disjuntos. Por favor, consulte la publicación a continuación para obtener más detalles.
Problema de secuenciación de trabajos | Conjunto 2 (usando conjunto disjunto)
Fuentes:
http://ocw.mit.edu/courses/civil-and-environmental-engineering/1-204-computer-algorithms-in-systems-engineering-spring-2010/lecture-notes/MIT1_204S10_lec10.pdf
Este artículo es aportado por Shubham . 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