Maximize jobs that can be completed under given constraint | C # Program to implement the above approach ; Function to find maxiumum number of jobs ; Min Heap ; Sort ranges by start day ; Stores the minimum and maximum day in the ranges ; Iterating from min_day to max_day ; Insert the end day of the jobs which can be completed on i - th day in a priority queue ; Pop all jobs whose end day is less than current day ; If queue is empty , no job can be completed on the i - th day ; Increment the count of jobs completed ; Pop the job with least end day ; Return the jobs on the last day ; Driver code
using System ; using System . Collections . Generic ; class GFG { static int find_maximum_jobs ( int N , List < Tuple < int , int > > ranges ) { List < int > queue = new List < int > ( ) ; ranges . Sort ( ) ; int min_day = ranges [ 0 ] . Item1 ; int max_day = 0 ; for ( int i = 0 ; i < N ; i ++ ) max_day = Math . Max ( max_day , ranges [ i ] . Item2 ) ; int index = 0 , count_jobs = 0 ; for ( int i = min_day ; i <= max_day ; i ++ ) { while ( index < ranges . Count && ranges [ index ] . Item1 <= i ) { queue . Add ( ranges [ index ] . Item2 ) ; index ++ ; } queue . Sort ( ) ; while ( queue . Count > 0 && queue [ 0 ] < i ) queue . RemoveAt ( 0 ) ; if ( queue . Count == 0 ) continue ; count_jobs ++ ; queue . RemoveAt ( 0 ) ; } return count_jobs ; } static void Main ( ) { int N = 5 ; List < Tuple < int , int > > ranges = new List < Tuple < int , int > > ( ) ; ranges . Add ( new Tuple < int , int > ( 1 , 5 ) ) ; ranges . Add ( new Tuple < int , int > ( 1 , 5 ) ) ; ranges . Add ( new Tuple < int , int > ( 1 , 5 ) ) ; ranges . Add ( new Tuple < int , int > ( 2 , 3 ) ) ; ranges . Add ( new Tuple < int , int > ( 2 , 3 ) ) ; Console . Write ( find_maximum_jobs ( N , ranges ) ) ; } }