MYSP.WeightJobSchedule

package specialproject2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class WeightJobSchedule {
    /**
     * Sort jobs by finish time.
     * For every job, find the first job which does not overlap with this job
     * and see if this job profit plus profit till last non overlapping job is greater than profit till last job.
     */

    public static int findLastNonConflictingJob(List<Job> jobs, int n)
	{
		// search space
		int low = 0;
		int high = n;

		// iterate till search space is not exhausted
		while (low <= high)
		{
			int mid = (low + high) / 2;
			if (jobs.get(mid).finishtime <= jobs.get(n).starttime) {
				if (jobs.get(mid + 1).finishtime <= jobs.get(n).starttime) {
					low = mid + 1;
				}
				else {
					return mid;
				}
			}
			else {
				high = mid - 1;
			}
		}

		// return negative index if no non-conflicting job is found
		return -1;
	}

    // Function to print the non-overlapping jobs involved in maximum profit
	// using Dynamic Programming
	public static void findMaxProfitJobs(List<Job> jobs)
	{
		// sort jobs in increasing order of their finish times
		Collections.sort(jobs, (x, y) -> x.finishtime - y.finishtime);

		// get number of jobs
		int n = jobs.size();

		// maxProfit[i] stores the maximum profit possible for the first i jobs and
		// tasks[i] stores the index of jobs involved in the maximum profit
		int[] maxProfit = new int[n];
		List<List<Integer>> tasks = new ArrayList<>(n);

		for (int i = 0; i < n; i++) {
			tasks.add(i, new ArrayList<>());
		}

		// initialize maxProfit[0] and tasks[0] with the first job
		maxProfit[0] = jobs.get(0).profit;
		tasks.get(0).add(0);

		// fill tasks[] and maxProfit[] in bottom-up manner
		for (int i = 1; i < n; i++)
		{
			// find the index of last non-conflicting job with current job
			int index = findLastNonConflictingJob(jobs, i);

			// include the current job with its non-conflicting jobs
			int currentProfit = jobs.get(i).profit;
			if (index != -1) {
				currentProfit += maxProfit[index];
			}

			// if including the current job leads to the maximum profit so far
			if (maxProfit[i-1] < currentProfit)
			{
				maxProfit[i] = currentProfit;

				if (index != -1) {
					tasks.set(i, tasks.get(index));
				}
				tasks.get(i).add(i);
			}

			// excluding the current job leads to the maximum profit so far
			else {
				tasks.set(i, tasks.get(i-1));
				maxProfit[i] = maxProfit[i-1];
			}
		}

		// maxProfit[n-1] stores the maximum profit
		System.out.println("The maximum profit is " + maxProfit[n-1]);

		// tasks[n-1] stores the index of jobs involved in the maximum profit
		System.out.print("The jobs involved in the maximum profit are: ");
		for (int i: tasks.get(n-1))
		{
			System.out.print("(" + jobs.get(i).starttime + ", " + jobs.get(i).finishtime + ", " + jobs.get(i).profit + ") ");
		}
	}



    public static void main(String[] args){
	List<Job> jobs = Arrays.asList(
            new Job( 0, 6, 2000 ),
            new Job( 1, 5, 530 ),
            new Job( 3, 5, 200 ),
            new Job( 5, 7, 680 ),
            new Job( 5, 9, 750 ),
            new Job( 7, 8, 100 ) );

        findMaxProfitJobs(jobs);
    }
}