Job Sequencing Problem using TreeSet in JAVA
Given an array of jobs where every job has a deadline and associated profit (if the job is finished before the deadline). It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.
Examples:
Input : Four Jobs with following deadlines and profits JobID Deadline Profit a 4 20 b 1 10 c 1 40 d 1 30 Output : Following is maximum profit sequence of jobs c, a
Input : Five Jobs with following deadlines and profits JobID Deadline Profit a 2 100 b 1 19 c 2 27 d 1 25 e 3 15 Output : Following is maximum profit sequence of jobs c, a, e
Below is the step by step algorithm to solve the problem using TreeSet in Java:
- Sort all the jobs according to their respective profits in decreasing order.
- Create a TreeSet and insert all the integers from 0 to n-1.
- Traverse the array of jobs and for ith job
- Search for a time slot ‘x’ in the TreeSet with maximum value which is less than the deadline of the ith job.
- If any value exists then include that job in the answer and remove ‘x’ from the TreeSet
- Else check for the remaining jobs.
Below is the implementation of the above algorithm:
import java.io.*; import java.util.*; public class Solution { // Job class public static class Job { char id; int deadline; int profit; // Constructor Job( char id, int deadline, int profit) { this .id = id; this .deadline = deadline; this .profit = profit; } } public static class Sorted implements Comparator { // Function to implement comparator public int compare(Object o1, Object o2) { Job j1 = (Job)o1; Job j2 = (Job)o2; if (j1.profit != j2.profit) return j2.profit - j1.profit; else return j2.deadline - j1.deadline; } } // Function to print job scheduling public static void printJobScheduling(Job jobs[], int n) { // Creating object of Sorted class Sorted sorter = new Sorted(); Arrays.sort(jobs, sorter); // Creating TreeSet Object TreeSet<Integer> ts = new TreeSet<>(); for ( int i = 0 ; i < n; i++) ts.add(i); for ( int i = 0 ; i < n; i++) { Integer x = ts.floor(jobs[i].deadline - 1 ); if (x != null ) { System.out.print(jobs[i].id + " " ); ts.remove(x); } } } // Driver Code public static void main(String[] args) { int n = 5 ; Job[] jobs = new Job[n]; jobs[ 0 ] = new Job( 'a' , 2 , 100 ); jobs[ 1 ] = new Job( 'b' , 1 , 19 ); jobs[ 2 ] = new Job( 'c' , 2 , 27 ); jobs[ 3 ] = new Job( 'd' , 1 , 25 ); jobs[ 4 ] = new Job( 'e' , 3 , 15 ); printJobScheduling(jobs, n); } // Contributed by Dipesh Jain (dipesh_jain) } |
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Contact Us