Activity Selection Problem | Greedy Algo | C ++ program for activity selection problem when input activities may not be sorted . ; A job has a start time , finish time and profit . ; A utility function that is used for sorting activities according to finish time ; Returns count of the maximum set of activities that can be done by a single person , one at a time . ; Sort jobs according to finish time ; The first activity always gets selected ; Consider rest of the activities ; If this activity has start time greater than or equal to the finish time of previously selected activity , then select it ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Activitiy { int start , finish ; } ; bool activityCompare ( Activitiy s1 , Activitiy s2 ) { return ( s1 . finish < s2 . finish ) ; } void printMaxActivities ( Activitiy arr [ ] , int n ) { sort ( arr , arr + n , activityCompare ) ; cout << " Following ▁ activities ▁ are ▁ selected ▁ n " ; int i = 0 ; cout << " ( " << arr [ i ] . start << " , ▁ " << arr [ i ] . finish << " ) , ▁ " ; for ( int j = 1 ; j < n ; j ++ ) { if ( arr [ j ] . start >= arr [ i ] . finish ) { cout << " ( " << arr [ j ] . start << " , ▁ " << arr [ j ] . finish << " ) , ▁ " ; i = j ; } } } int main ( ) { Activitiy arr [ ] = { { 5 , 9 } , { 1 , 2 } , { 3 , 4 } , { 0 , 6 } , { 5 , 7 } , { 8 , 9 } } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printMaxActivities ( arr , n ) ; return 0 ; }