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
def canPlace ( a , n , p , sep ) : NEW_LINE INDENT prisoners_placed = 1 NEW_LINE last_prisoner_placed = a [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT current_cell = a [ i ] NEW_LINE if ( current_cell - last_prisoner_placed >= sep ) : NEW_LINE INDENT prisoners_placed += 1 NEW_LINE last_prisoner_placed = current_cell NEW_LINE if ( prisoners_placed == p ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT def maxDistance ( cell , n , p ) : NEW_LINE INDENT cell = sorted ( cell ) NEW_LINE start = 0 NEW_LINE end = cell [ n - 1 ] - cell [ 0 ] NEW_LINE ans = 0 NEW_LINE while ( start <= end ) : NEW_LINE INDENT mid = start + ( ( end - start ) // 2 ) NEW_LINE if ( canPlace ( cell , n , p , mid ) ) : NEW_LINE INDENT ans = mid NEW_LINE start = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT end = mid - 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT cell = [ 1 , 2 , 8 , 4 , 9 ] NEW_LINE n = len ( cell ) NEW_LINE p = 3 NEW_LINE print ( maxDistance ( cell , n , p ) ) NEW_LINE