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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int find_maximum_jobs ( int N , vector < pair < int , int > > ranges ) { priority_queue < int , vector < int > , greater < int > > queue ; sort ( ranges . begin ( ) , ranges . end ( ) ) ; int min_day = ranges [ 0 ] . first ; int max_day = 0 ; for ( int i = 0 ; i < N ; i ++ ) max_day = max ( max_day , ranges [ i ] . second ) ; int index = 0 , count_jobs = 0 ; for ( int i = min_day ; i <= max_day ; i ++ ) { while ( index < ranges . size ( ) && ranges [ index ] . first <= i ) { queue . push ( ranges [ index ] . second ) ; index ++ ; } while ( ! queue . empty ( ) && queue . top ( ) < i ) queue . pop ( ) ; if ( queue . empty ( ) ) continue ; count_jobs ++ ; queue . pop ( ) ; } return count_jobs ; } int main ( ) { int N = 5 ; vector < pair < int , int > > ranges ; ranges . push_back ( { 1 , 5 } ) ; ranges . push_back ( { 1 , 5 } ) ; ranges . push_back ( { 1 , 5 } ) ; ranges . push_back ( { 2 , 3 } ) ; ranges . push_back ( { 2 , 3 } ) ; cout << find_maximum_jobs ( N , ranges ) ; }