Place the prisoners into cells to maximize the minimum difference between any two | Function that returns true if the prisoners can be placed such that the minimum distance between any two prisoners is at least sep ; Considering the first prisoner is placed at 1 st cell ; If the first prisoner is placed at the first cell then the last_prisoner_placed will be the first prisoner placed and that will be in cell [ 0 ] ; Checking if the prisoner can be placed at ith cell or not ; If all the prisoners got placed then return true ; Function to return the maximized distance ; Sort the array so that binary search can be applied on it ; Minimum possible distance for the search space ; Maximum possible distance for the search space ; To store the result ; Binary search ; If the prisoners can be placed such that the minimum distance between any two prisoners is at least mid ; Update the answer ; Driver code
function canPlace ( a , n , p , sep ) { var prisoners_placed = 1 ; var last_prisoner_placed = a [ 0 ] ; for ( i = 1 ; i < n ; i ++ ) { var current_cell = a [ i ] ; if ( current_cell - last_prisoner_placed >= sep ) { prisoners_placed ++ ; last_prisoner_placed = current_cell ; if ( prisoners_placed == p ) { return true ; } } } return false ; } function maxDistance ( cell , n , p ) { cell . sort ( ) ; var start = 0 ; var end = cell [ n - 1 ] - cell [ 0 ] ; var ans = 0 ; while ( start <= end ) { var mid = start + parseInt ( ( ( end - start ) / 2 ) ) ; if ( canPlace ( cell , n , p , mid ) ) { ans = mid ; start = mid + 1 ; } else { end = mid - 1 ; } } return ans ; } var cell = [ 1 , 2 , 8 , 4 , 9 ] ; var n = cell . length ; var p = 3 ; document . write ( maxDistance ( cell , n , p ) ) ;