Programación ponderada de trabajos en tiempo O(n Log n)

Dados N trabajos donde cada trabajo está representado por los siguientes tres elementos.

1. Hora de inicio
2. Tiempo de finalización
3. Beneficio o valor asociado

Encuentre el subconjunto de trabajos de ganancia máxima tal que no haya dos trabajos en el subconjunto que se superpongan.
Ejemplo: 

Input: Number of Jobs n = 4
       Job Details {Start Time, Finish Time, Profit}
       Job 1:  {1, 2, 50} 
       Job 2:  {3, 5, 20}
       Job 3:  {6, 19, 100}
       Job 4:  {2, 100, 200}
Output: The maximum profit is 250.
We can get the maximum profit by scheduling jobs 1 and 4.
Note that there is longer schedules possible Jobs 1, 2 and 3 
but the profit with this schedule is 20+50+100 which is less than 250.  

Recomendamos encarecidamente consultar el siguiente artículo como requisito previo para ello. 
Programación ponderada
de trabajos El problema anterior se puede resolver utilizando la siguiente solución recursiva. 
 

1) First sort jobs according to finish time.
2) Now apply following recursive process. 
   // Here arr[] is array of n jobs
   findMaximumProfit(arr[], n)
   {
     a) if (n == 1) return arr[0];
     b) Return the maximum of following two profits.
         (i) Maximum profit by excluding current job, i.e., 
             findMaximumProfit(arr, n-1)
         (ii) Maximum profit by including the current job            
   }

How to find the profit including current job?
The idea is to find the latest job before the current job (in 
sorted array) that doesn't conflict with current job 'arr[n-1]'. 
Once we find such a job, we recur for all jobs till that job and
add profit of current job to result.
In the above example, "job 1" is the latest non-conflicting
for "job 4" and "job 2" is the latest non-conflicting for "job 3".

Hemos discutido enfoques recursivos y basados ​​en Programación Dinámica en el artículo anterior . Las implementaciones discutidas en la publicación anterior utilizan la búsqueda lineal para encontrar el trabajo anterior sin conflicto. En esta publicación, se analiza la solución basada en la búsqueda binaria. La complejidad temporal de la solución basada en la búsqueda binaria es O(n Log n).
El algoritmo es: 
 

1. Ordene los trabajos por tiempos de finalización no decrecientes.
2. Para cada i de 1 a n, determine el valor máximo del programa a partir de la subsecuencia de trabajos [0..i]. Haga esto comparando la inclusión de trabajo[i] en el horario con la exclusión de trabajo[i] en el horario, y luego tomando el máximo.

Para encontrar el beneficio con la inclusión del trabajo[i]. necesitamos encontrar el trabajo más reciente que no entre en conflicto con trabajo[i]. La idea es utilizar la búsqueda binaria para encontrar el trabajo más reciente que no esté en conflicto.
 

// C++ program for weighted job scheduling using Dynamic 
// Programming and Binary Search
#include <iostream>
#include <algorithm>
using namespace std;
   
// A job has start time, finish time and profit.
struct Job
{
    int start, finish, profit;
};
   
// A utility function that is used for sorting events
// according to finish time
bool myfunction(Job s1, Job s2)
{
    return (s1.finish < s2.finish);
}
   
// A Binary Search based function to find the latest job
// (before current job) that doesn't conflict with current
// job.  "index" is index of the current job.  This function
// returns -1 if all jobs before index conflict with it.
// The array jobs[] is sorted in increasing order of finish
// time.
int binarySearch(Job jobs[], int index)
{
    // Initialize 'lo' and 'hi' for Binary Search
    int lo = 0, hi = index - 1;
   
    // Perform binary Search iteratively
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (jobs[mid].finish <= jobs[index].start)
        {
            if (jobs[mid + 1].finish <= jobs[index].start)
                lo = mid + 1;
            else
                return mid;
        }
        else
            hi = mid - 1;
    }
   
    return -1;
}
   
// The main function that returns the maximum possible
// profit from given array of jobs
int findMaxProfit(Job arr[], int n)
{
    // Sort jobs according to finish time
    sort(arr, arr+n, myfunction);
   
    // Create an array to store solutions of subproblems.  table[i]
    // stores the profit for jobs till arr[i] (including arr[i])
    int *table = new int[n];
    table[0] = arr[0].profit;
   
    // Fill entries in table[] using recursive property
    for (int i=1; i<n; i++)
    {
        // Find profit including the current job
        int inclProf = arr[i].profit;
        int l = binarySearch(arr, i);
        if (l != -1)
            inclProf += table[l];
   
        // Store maximum of including and excluding
        table[i] = max(inclProf, table[i-1]);
    }
   
    // Store result and free dynamic memory allocated for table[]
    int result = table[n-1];
    delete[] table;
    
    return result;
}
   
// Driver program
int main()
{
    Job arr[] = {{3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Optimal profit is " << findMaxProfit(arr, n);
    return 0;
}

// Java program for Weighted Job Scheduling in O(nLogn)
// time
import java.util.Arrays;
import java.util.Comparator;
 
// Class to represent a job
class Job
{
    int start, finish, profit;
 
    // Constructor
    Job(int start, int finish, int profit)
    {
        this.start = start;
        this.finish = finish;
        this.profit = profit;
    }
}
 
// Used to sort job according to finish times
class JobComparator implements Comparator<Job>
{
    public int compare(Job a, Job b)
    {
        return a.finish < b.finish ? -1 : a.finish == b.finish ? 0 : 1;
    }
}
 
public class WeightedIntervalScheduling
{
    /* A Binary Search based function to find the latest job
      (before current job) that doesn't conflict with current
      job.  "index" is index of the current job.  This function
      returns -1 if all jobs before index conflict with it.
      The array jobs[] is sorted in increasing order of finish
      time. */
    static public int binarySearch(Job jobs[], int index)
    {
        // Initialize 'lo' and 'hi' for Binary Search
        int lo = 0, hi = index - 1;
 
        // Perform binary Search iteratively
        while (lo <= hi)
        {
            int mid = (lo + hi) / 2;
            if (jobs[mid].finish <= jobs[index].start)
            {
                if (jobs[mid + 1].finish <= jobs[index].start)
                    lo = mid + 1;
                else
                    return mid;
            }
            else
                hi = mid - 1;
        }
 
        return -1;
    }
 
    // The main function that returns the maximum possible
    // profit from given array of jobs
    static public int schedule(Job jobs[])
    {
        // Sort jobs according to finish time
        Arrays.sort(jobs, new JobComparator());
 
        // Create an array to store solutions of subproblems.
        // table[i] stores the profit for jobs till jobs[i]
        // (including jobs[i])
        int n = jobs.length;
        int table[] = new int[n];
        table[0] = jobs[0].profit;
 
        // Fill entries in M[] using recursive property
        for (int i=1; i<n; i++)
        {
            // Find profit including the current job
            int inclProf = jobs[i].profit;
            int l = binarySearch(jobs, i);
            if (l != -1)
                inclProf += table[l];
 
            // Store maximum of including and excluding
            table[i] = Math.max(inclProf, table[i-1]);
        }
 
        return table[n-1];
    }
 
    // Driver method to test above
    public static void main(String[] args)
    {
        Job jobs[] = {new Job(1, 2, 50), new Job(3, 5, 20),
                      new Job(6, 19, 100), new Job(2, 100, 200)};
 
        System.out.println("Optimal profit is " + schedule(jobs));
    }
}

# Python program for weighted job scheduling using Dynamic
# Programming and Binary Search
 
# Class to represent a job
class Job:
    def __init__(self, start, finish, profit):
        self.start  = start
        self.finish = finish
        self.profit  = profit
 
 
# A Binary Search based function to find the latest job
# (before current job) that doesn't conflict with current
# job.  "index" is index of the current job.  This function
# returns -1 if all jobs before index conflict with it.
# The array jobs[] is sorted in increasing order of finish
# time.
def binarySearch(job, start_index):
 
    # Initialize 'lo' and 'hi' for Binary Search
    lo = 0
    hi = start_index - 1
 
    # Perform binary Search iteratively
    while lo <= hi:
        mid = (lo + hi) // 2
        if job[mid].finish <= job[start_index].start:
            if job[mid + 1].finish <= job[start_index].start:
                lo = mid + 1
            else:
                return mid
        else:
            hi = mid - 1
    return -1
 
# The main function that returns the maximum possible
# profit from given array of jobs
def schedule(job):
   
    # Sort jobs according to finish time
    job = sorted(job, key = lambda j: j.finish)
 
    # Create an array to store solutions of subproblems.  table[i]
    # stores the profit for jobs till arr[i] (including arr[i])
    n = len(job)
    table = [0 for _ in range(n)]
 
    table[0] = job[0].profit;
 
    # Fill entries in table[] using recursive property
    for i in range(1, n):
 
        # Find profit including the current job
        inclProf = job[i].profit
        l = binarySearch(job, i)
        if (l != -1):
            inclProf += table[l];
 
        # Store maximum of including and excluding
        table[i] = max(inclProf, table[i - 1])
 
    return table[n-1]
 
# Driver code to test above function
job = [Job(1, 2, 50), Job(3, 5, 20),
      Job(6, 19, 100), Job(2, 100, 200)]
print("Optimal profit is"),
print schedule(job)

<script>
 
// JavaScript program for weighted job scheduling using Dynamic
// Programming and Binary Search
 
// Class to represent a job
class Job{
    constructor(start, finish, profit){
        this.start = start
        this.finish = finish
        this.profit = profit
    }
}
 
// A Binary Search based function to find the latest job
// (before current job) that doesn't conflict with current
// job. "index" is index of the current job. This function
// returns -1 if all jobs before index conflict with it.
// The array jobs[] is sorted in increasing order of finish
// time.
function binarySearch(job, start_index){
 
    // Initialize 'lo' and 'hi' for Binary Search
    let lo = 0
    let hi = start_index - 1
 
    // Perform binary Search iteratively
    while(lo <= hi){
        let mid = Math.floor((lo + hi) /2);
        if (job[mid].finish <= job[start_index].start){
            if(job[mid + 1].finish <= job[start_index].start)
                lo = mid + 1
            else
                return mid
        }
        else
            hi = mid - 1
    }
 
    return -1
 
}
 
// The main function that returns the maximum possible
// profit from given array of jobs
function schedule(job){
     
    // Sort jobs according to finish time
    job.sort((a,b)=>a.finish - b.finish)
 
    // Create an array to store solutions of subproblems. table[i]
    // stores the profit for jobs till arr[i] (including arr[i])
    let n = job.length
    let table = new Array(n).fill(0)
 
    table[0] = job[0].profit;
 
    // Fill entries in table[] using recursive property
    for(let i=1;i<n;i++){
 
        // Find profit including the current job
        inclProf = job[i].profit
        l = binarySearch(job, i)
        if (l != -1)
            inclProf += table[l];
 
        // Store maximum of including and excluding
        table[i] = Math.max(inclProf, table[i - 1])
    }
 
    return table[n-1]
}
 
// Driver code to test above function
let job = [new Job(1, 2, 50), new Job(3, 5, 20),
    new Job(6, 19, 100), new Job(2, 100, 200)]
     
document.write("Optimal profit is ")
document.write(schedule(job),"</br>")
 
// This code is contributed by shinjanpatra.
</script>

Producción:

Optimal profit is 250

Este artículo es una contribución de Daniel Ray . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.