Question

java code for scheduling problem (start time,end time , profite) using greedy algorithm

Answer 1

The following code consists of 2 classes one named job and other named Scheduling(contains Main). In order to run the code either save the code with this name (Scheduling) if using any IDE or run the class Scheduling if using CMD.

SOURCE CODE

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~// Java program for Scheduling in O(nLogn) time
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

// 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;
   }
   Job()
   {}
}

// 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;
   }
}

class Scheduling
{
   /* 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)
       {
             Scanner s = new Scanner(System.in);
              System.out.print("Enter number of jobs you want: ");
              int n= s.nextInt();
            Job jobs[] = new Job[n];
           for ( int i=0; i<n; i++)
                   {
                      jobs[i]=new Job();
                  System.out.println("\nFor Job "+i);
                   System.out.println("Start Time: ");
                      jobs[i].start = s.nextInt();   // s is a Scanner object
                        System.out.println("End Time: ");
                       jobs[i].finish = s.nextInt();
                   System.out.println("Profit: ");
                        jobs[i].profit = s.nextInt();
                       System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
                }    

       System.out.println("Optimal profit is " + schedule(jobs));
    }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

For further queries in this code ask in comment. Please leave a rating/upvote. Cheers!