Find minimum speed to finish all Jobs | CPP program to find minimum speed to finish all jobs ; Function to check if the person can do all jobs in H hours with speed K ; Function to return the minimum speed of person to complete all jobs ; If H < N it is not possible to complete all jobs as person can not move from one element to another during current hour ; Max element of array ; Use binary search to find smallest K ; Driver program ; Print required maxLenwer
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPossible ( int A [ ] , int n , int H , int K ) { int time = 0 ; for ( int i = 0 ; i < n ; ++ i ) time += ( A [ i ] - 1 ) / K + 1 ; return time <= H ; } int minJobSpeed ( int A [ ] , int n , int H ) { if ( H < n ) return -1 ; int * max = max_element ( A , A + n ) ; int lo = 1 , hi = * max ; while ( lo < hi ) { int mi = lo + ( hi - lo ) / 2 ; if ( ! isPossible ( A , n , H , mi ) ) lo = mi + 1 ; else hi = mi ; } return lo ; } int main ( ) { int A [ ] = { 3 , 6 , 7 , 11 } , H = 8 ; int n = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << minJobSpeed ( A , n , H ) ; return 0 ; }