Question

Using java create the following program and post the answer as well.

The Weighted Interval Scheduling problem is this: Given a set of weighted intervals, choose a set of non-overlapping intervals such that the total weight is maximal. You may think of the “weight” as the profit for doing the work in the given interval

A weighted interval x can be represented by a triple

       x = (s, f, v),

where

         s = start time of x,    f = finish time of x,   v = weight or profit of this job

For example, consider the test case for Weighted Interval Scheduling problem depicted below:

3 2 5 2 3 0 12345678

These weighted intervals can be represented by the triples

         (0,3,3) (1,4,2) (0,5,4) (3,6,1) (4,7,2) (3,9,5) (5,10,2) (8,10,1)

Write a program to compute a solution to the Weighted Interval Scheduling problem.

Your program must read in a set of weighted intervals. Each interval should be entered as 3 integers. The intervals must be given in a textfile and also be entered in increasing order of finish time. In the above case we would have

            0 3 3    1 4 2    0 5 4    3 6 1   ...

The program must print out the value of the total weight or profit of the optimum solution and the indices of the jobs. The output must be in the following format (the output below does NOT have the correct result).

     Optimum profit: 7

     Usng Jobs: 2 5

The program MUST use recursion. An iterative solution will not receive full credit. Use of memoization will receive 20 points extra credit.

You must submit a run using the example above. You must also submit a run using the following sample data set:

         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}

In both cases you must submit a printout of the input file used.

Answer 1

WeightedJobScheduling.java

import java.util.Arrays;
import java.util.Comparator;

/**
* Weighted Job Scheduling
*
* Given N jobs where every job is represented by following three elements of
* it. 1) Start Time 2) Finish Time. 3) Profit or Value Associated. Find the
* maximum profit subset of jobs such that no two jobs in the subset overlap.
*
* Example:
*
* 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.
*
*/

class Job {
    int start;
    int end;
    int profit;

    public Job(int start, int end, int profit) {
   super();
   this.start = start;
   this.end = end;
   this.profit = profit;
    }
}

public class WeightedJobScheduling {
    class Solution {
   int findMaxProfit(Job[] jobs) {
        if (jobs == null || jobs.length == 0) {
       return 0;
        } else if (jobs.length == 1) {
       return jobs[0].profit;
        }

        Arrays.sort(jobs, new Comparator<Job>() {
       @Override
       public int compare(Job j1, Job j2) {
            return j1.end - j2.end;
       }
        });

        int[] dp = new int[jobs.length];
        dp[0] = jobs[0].profit;

        for (int i = 1; i < jobs.length; i++) {
       // Find the latest job (in sorted array) that doesn't
       // conflict with the job[i]
       int j = i - 1;
       while (j >= 0 && jobs[j].end > jobs[i].start) {
            j--;
       }
      
       int include = jobs[i].profit + (j >= 0 ? dp[j] : 0);
       dp[i] = Math.max(include, dp[i-1]);
        }

        return dp[dp.length-1];
   }
    }

    public static void main(String[] args) {
   Job[] jobs = new Job[] { new Job(3, 10, 20), new Job(1, 2, 50),
       new Job(6, 19, 100), new Job(2, 100, 200) };
   System.out.println(new WeightedJobScheduling().new Solution()
       .findMaxProfit(jobs));
    }
}

Problems Javadoc Declaration Conso Coverage <terminated> WeightedJobScheduling Java Application] CProgram Files Javaljdk1.8.0 131\binljavaw.exe (Oct 30, 2017,9:58:35 PM) 250