Weighted Job Scheduling | Set 2 ( Using LIS ) | C ++ program for weighted job scheduling using LIS ; A job has start time , finish time and profit . ; Utility function to calculate sum of all vector elements ; comparator function for sort function ; 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 Function
#include <iostream> NEW_LINE #include <vector> NEW_LINE #include <algorithm> NEW_LINE using namespace std ; struct Job { int start , finish , profit ; } ; int findSum ( vector < Job > arr ) { int sum = 0 ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) sum += arr [ i ] . profit ; return sum ; } int compare ( Job x , Job y ) { return x . start < y . start ; } void findMaxProfit ( vector < Job > & arr ) { sort ( arr . begin ( ) , arr . end ( ) , compare ) ; vector < vector < Job > > L ( arr . size ( ) ) ; L [ 0 ] . push_back ( arr [ 0 ] ) ; for ( int i = 1 ; i < arr . size ( ) ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( ( arr [ j ] . finish <= arr [ i ] . start ) && ( findSum ( L [ j ] ) > findSum ( L [ i ] ) ) ) L [ i ] = L [ j ] ; } L [ i ] . push_back ( arr [ i ] ) ; } vector < Job > maxChain ; for ( int i = 0 ; i < L . size ( ) ; i ++ ) if ( findSum ( L [ i ] ) > findSum ( maxChain ) ) maxChain = L [ i ] ; for ( int i = 0 ; i < maxChain . size ( ) ; i ++ ) cout << " ( " << maxChain [ i ] . start << " , ▁ " << maxChain [ i ] . finish << " , ▁ " << maxChain [ i ] . profit << " ) ▁ " ; } int main ( ) { Job a [ ] = { { 3 , 10 , 20 } , { 1 , 2 , 50 } , { 6 , 19 , 100 } , { 2 , 100 , 200 } } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; vector < Job > arr ( a , a + n ) ; findMaxProfit ( arr ) ; return 0 ; }