Maximize jobs that can be completed under given constraint | 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
def find_maximum_jobs ( N , ranges ) : NEW_LINE INDENT queue = [ ] NEW_LINE ranges . sort ( ) NEW_LINE min_day = ranges [ 0 ] [ 0 ] NEW_LINE max_day = 0 NEW_LINE for i in range ( N ) : NEW_LINE max_day = max ( max_day , ranges [ i ] [ 1 ] ) NEW_LINE index , count_jobs = 0 , 0 NEW_LINE for i in range ( min_day , max_day + 1 ) : NEW_LINE while ( index < len ( ranges ) and ranges [ index ] [ 0 ] <= i ) : NEW_LINE INDENT queue . append ( ranges [ index ] [ 1 ] ) NEW_LINE index += 1 NEW_LINE DEDENT queue . sort ( ) NEW_LINE while ( len ( queue ) > 0 and queue [ 0 ] < i ) : NEW_LINE INDENT queue . pop ( 0 ) NEW_LINE DEDENT if ( len ( queue ) == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT count_jobs += 1 NEW_LINE queue . pop ( 0 ) NEW_LINE return count_jobs NEW_LINE DEDENT N = 5 NEW_LINE ranges = [ ] NEW_LINE ranges . append ( ( 1 , 5 ) ) NEW_LINE ranges . append ( ( 1 , 5 ) ) NEW_LINE ranges . append ( ( 1 , 5 ) ) NEW_LINE ranges . append ( ( 2 , 3 ) ) NEW_LINE ranges . append ( ( 2 , 3 ) ) NEW_LINE print ( find_maximum_jobs ( N , ranges ) ) NEW_LINE