Maximize jobs that can be completed under given constraint | Java 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
import java . io . * ; import java . util . * ; class GFG { static int find_maximum_jobs ( int N , ArrayList < ArrayList < Integer > > ranges ) { ArrayList < Integer > queue = new ArrayList < Integer > ( ) ; Collections . sort ( ranges , new Comparator < ArrayList < Integer > > ( ) { @ Override public int compare ( ArrayList < Integer > o1 , ArrayList < Integer > o2 ) { return o1 . get ( 0 ) . compareTo ( o2 . get ( 0 ) ) ; } } ) ; int min_day = ranges . get ( 0 ) . get ( 0 ) ; int max_day = 0 ; for ( int i = 0 ; i < N ; i ++ ) max_day = Math . max ( max_day , ranges . get ( i ) . get ( 1 ) ) ; int index = 0 , count_jobs = 0 ; for ( int i = min_day ; i <= max_day ; i ++ ) { while ( index < ranges . size ( ) && ranges . get ( index ) . get ( 0 ) <= i ) { queue . add ( ranges . get ( index ) . get ( 1 ) ) ; index ++ ; } Collections . sort ( queue ) ; while ( queue . size ( ) > 0 && queue . get ( 0 ) < i ) queue . remove ( 0 ) ; if ( queue . size ( ) == 0 ) continue ; count_jobs ++ ; queue . remove ( 0 ) ; } return count_jobs ; } public static void main ( String [ ] args ) { int N = 5 ; ArrayList < ArrayList < Integer > > ranges = new ArrayList < ArrayList < Integer > > ( ) ; ranges . add ( new ArrayList < Integer > ( Arrays . asList ( 1 , 5 ) ) ) ; ranges . add ( new ArrayList < Integer > ( Arrays . asList ( 1 , 5 ) ) ) ; ranges . add ( new ArrayList < Integer > ( Arrays . asList ( 1 , 5 ) ) ) ; ranges . add ( new ArrayList < Integer > ( Arrays . asList ( 2 , 3 ) ) ) ; ranges . add ( new ArrayList < Integer > ( Arrays . asList ( 2 , 3 ) ) ) ; System . out . println ( find_maximum_jobs ( N , ranges ) ) ; } }