Question

Given the following jobs to schedule (already ordered): job numberstart time finish timevalue 6 10 2 6 4 8 6 What will the Pü) values in the predecessor table be? Enter the first 3 values, for jobs 1 to 3 (in that order), here: Enter the next 3 values, for jobs 4 to 6 (in that order), here: Question 16 (6 points) from the previous question, what values will be in the optimal benefit table, B? Enter the first 3 values, for jobs 1 to 3 (in that order) here Enter the next 3 values, for jobs 4 to 6 (in that order) here Question 17 (3 points) Continuing the same job scheduling problem from the previous 2 questions which jobs will be scheduled to achieve the optimal benefit? Enter the job numbers, in ascending order, separated by spaces. For example 145

Answer 1

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.

#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 jobComparataor(Job s1, Job s2)
{
    return (s1.finish < s2.finish);
}

// Find the latest job (in sorted array) that doesn't
// conflict with the job[i]
int latestNonConflict(Job arr[], int i)
{
    for (int j=i-1; j>=0; j--)
    {
        if (arr[j].finish <= arr[i].start)
            return j;
    }
    return -1;
}

// A recursive function that returns the maximum possible
// profit from given array of jobs. The array of jobs must
// be sorted according to finish time.
int findMaxProfitRec(Job arr[], int n)
{
    // Base case
    if (n == 1) return arr[n-1].profit;

    // Find profit when current job is inclueded
    int inclProf = arr[n-1].profit;
    int i = latestNonConflict(arr, n);
    if (i != -1)
      inclProf += findMaxProfitRec(arr, i+1);

    // Find profit when current job is excluded
    int exclProf = findMaxProfitRec(arr, n-1);

    return max(inclProf, exclProf);
}

// 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, jobComparataor);

    return findMaxProfitRec(arr, n);
}

// The main function that returns the maximum possible
// profit from given array of jobs
int findMaxProfit_dp(Job arr[], int n)
{
    // Sort jobs according to finish time
    sort(arr, arr+n, jobComparataor);

    // 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 M[] using recursive property
    for (int i=1; i<n; i++)
    {
        // Find profit including the current job
        int inclProf = arr[i].profit;
        int l = latestNonConflict(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[] = {{1,3,5},{1,5,6},{2,6,10},{3,6,4},{5,8,6},{6,8,3}};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "The optimal profit is " << findMaxProfit_dp(arr, n);
    cout << "Greedy profit is " << findMaxProfit(arr, n);
    return 0;
}

Question 15:

2, 1, 3

4, 6, 5

Question 16:

3, 2, 1

4, 6, 5

Question 17:

1, 5