Job sequencing is a type of problem that looks for a job order where jobs can be completed within their deadlines and achieve maximum profit.
First, we create an object to save the given data in terms of:
id - id
dl - deadline
pr - profit.
public Main(String id, int dl, int pr)
{
this.id = id;
this.dl = dl;
this.pr = pr;
}
We also need the max function to find the highest deadline in the given input.
int max(ArrayList<Main> array)
{
int max = array.get(0).dl;
for (int i = 1; i < array.size(); i++)
if (array.get(i).dl > max)
max = array.get(i).dl;
return max;
}
In the printJobScheduling function we first sort the arraylist, according to the profits, inside the for loop.
Hence, we can gradually look up each object and check if the slot is available based on the boolean array.
Boolean array is created to enable us to track available slots.
Collections.sort(array,
(a, b) -> b.pr - a.pr);
boolean result[] = new boolean[t];
String job[] = new String[t];
for (int i = 0; i < n; i++)
{
int index=array.get(i).dl-1;
if (result[index] == false)
{
result[index] = true;
job[index] = array.get(i).id;
profit += array.get(i).pr;
}
}
The final implementation for the above table is:
import java.util.*;class Main{String id;int dl, pr;public Main() {}public Main(String id, int dl, int pr){this.id = id;this.dl = dl;this.pr = pr;}int max(ArrayList<Main> array){int max = array.get(0).dl;for (int i = 1; i < array.size(); i++)if (array.get(i).dl > max)max = array.get(i).dl;return max;}void printJobScheduling(ArrayList<Main> array){int profit=0;int n = array.size();int t = max(array);Collections.sort(array,(a, b) -> b.pr - a.pr);boolean result[] = new boolean[t];String job[] = new String[t];for (int i = 0; i < n; i++){int index=array.get(i).dl-1;if (result[index] == false){result[index] = true;job[index] = array.get(i).id;profit += array.get(i).pr;}}for (String jb : job){System.out.print(jb + " ");}System.out.println();System.out.println(profit);}public static void main(String args[]){ArrayList<Main> array = new ArrayList<Main>();array.add(new Main("J1", 2, 60));array.add(new Main("J2", 1, 100));array.add(new Main("J3", 3, 20));array.add(new Main("J4", 2, 40));array.add(new Main("J5", 1, 20));Main job = new Main();job.printJobScheduling(array);}}