Weighted Job Scheduling | Set 2 ( Using LIS ) | Java program for weighted job scheduling using LIS ; A job has start time , finish time and profit . ; Utility function to calculate sum of all ArrayList elements ; The main function that finds the maximum possible profit from given array of jobs ; Sort arr [ ] by start time . ; L [ i ] stores stores Weighted Job Scheduling of job [ 0. . i ] that ends with job [ i ] ; L [ 0 ] is equal to arr [ 0 ] ; Start from index 1 ; For every j less than i ; L [ i ] = { MaxSum ( L [ j ] ) } + arr [ i ] where j < i and arr [ j ] . finish <= arr [ i ] . start ; Find one with max profit ; Driver code
import java . util . ArrayList ; import java . util . Arrays ; import java . util . Collections ; import java . util . Comparator ; class Graph { static class Job { int start , finish , profit ; public Job ( int start , int finish , int profit ) { this . start = start ; this . finish = finish ; this . profit = profit ; } } ; static int findSum ( ArrayList < Job > arr ) { int sum = 0 ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) sum += arr . get ( i ) . profit ; return sum ; } static void findMaxProfit ( ArrayList < Job > arr ) { Collections . sort ( arr , new Comparator < Job > ( ) { @ Override public int compare ( Job x , Job y ) { return x . start - y . start ; } } ) ; ArrayList < ArrayList < Job > > L = new ArrayList < > ( ) ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) { L . add ( new ArrayList < > ( ) ) ; } L . get ( 0 ) . add ( arr . get ( 0 ) ) ; for ( int i = 1 ; i < arr . size ( ) ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( ( arr . get ( j ) . finish <= arr . get ( i ) . start ) && ( findSum ( L . get ( j ) ) > findSum ( L . get ( i ) ) ) ) { ArrayList < Job > copied = new ArrayList < > ( L . get ( j ) ) ; L . set ( i , copied ) ; } } L . get ( i ) . add ( arr . get ( i ) ) ; } ArrayList < Job > maxChain = new ArrayList < > ( ) ; for ( int i = 0 ; i < L . size ( ) ; i ++ ) if ( findSum ( L . get ( i ) ) > findSum ( maxChain ) ) maxChain = L . get ( i ) ; for ( int i = 0 ; i < maxChain . size ( ) ; i ++ ) { System . out . printf ( "(%d, %d, %d)NEW_LINE", maxChain . get ( i ) . start , maxChain . get ( i ) . finish , maxChain . get ( i ) . profit ) ; } } public static void main ( String [ ] args ) { Job [ ] a = { new Job ( 3 , 10 , 20 ) , new Job ( 1 , 2 , 50 ) , new Job ( 6 , 19 , 100 ) , new Job ( 2 , 100 , 200 ) } ; ArrayList < Job > arr = new ArrayList < > ( Arrays . asList ( a ) ) ; findMaxProfit ( arr ) ; } }