Encuentre la velocidad mínima para terminar todos los trabajos

Dada una array A y un entero H donde  y  . Cada elemento A[i] representa los trabajos pendientes restantes por realizar y H representa las horas que quedan para completar todos los trabajos. La tarea es encontrar la velocidad mínima en trabajos por hora a la que la persona necesita trabajar para completar todos los trabajos en H horas.
Nota: Si A[i] tiene menos trabajo por hacer que la velocidad de la persona , entonces terminará todo el trabajo de A[i] y no pasará al siguiente elemento durante esta hora.
Ejemplos : 
 

Input: A[] = [3, 6, 7, 11], H = 8
Output: 4

Input: A[] = [30, 11, 23, 4, 20], H = 5
Output: 30

Enfoque: si la persona puede terminar todos los trabajos (dentro de H horas) con una velocidad de K trabajos/hora, entonces también puede terminar todos los trabajos a una velocidad mayor.
Si hacemos que ispossible(K) sea verdadero si y solo si la persona puede terminar con una velocidad de trabajo de K , entonces hay algún X tal que ispossible(K) = True si y solo si K >= X.
Por ejemplo, con A = [3, 6, 7, 11] y H = 8 , hay algo de X = 4 , por lo que es posible (1) = es posible (2) = es posible (3) = Falso y es posible (4) = es posible(5) = … = Verdadero .
Podemos hacer una búsqueda binaria sobre los valores de ispossible(K) para encontrar la primera X tal que ispossible(X) sea True , que será nuestra respuesta.
Ahora, como no está permitido pasar de un elemento a otro durante la hora actual, incluso si el trabajo se completa, el valor máximo posible de K puede ser el elemento máximo en la array A[]. Entonces, para encontrar el valor de ispossible(K) , (es decir, si una persona con una velocidad de trabajo de K puede terminar todos los trabajos en H horas), realice una búsqueda binaria en el rango (1, max_element_of_array).
Además, por cada A[i] de trabajos > 0, podemos deducir que esa persona lo termina en Math.ceil(A[i] / K)o ((A[i]-1) / K) + 1 horas, y sumamos estos para todos los elementos para encontrar el tiempo total para completar todos los trabajos y compararlo con H para verificar si es posible terminar todos los trabajos con una velocidad de K trabajos/hora. 
A continuación se muestra la implementación del enfoque anterior: 
 

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

// Java program to find minimum speed
// to finish all jobs
class GFG
{
 
// Function To findmax value in Array
static int findmax(int[] A)
{
    int r = A[0];
    for(int i = 1; i < A.length; i++)
    r = Math.max(r, A[i]);
    return r;
}
 
// Function to check if the person can do
// all jobs in H hours with speed K
static boolean 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;
}
 
// Function to return the minimum speed
// of person to complete all jobs
static int minJobSpeed(int[] A,
                       int n, int H)
{
    // If H < N it is not possible to
    // complete all jobs as person can
    // not move from one element to
    // another during current hour
    if (H < n)
        return -1;
 
    // Max element of array
    int max = findmax(A);
 
    int lo = 1, hi = max;
 
    // Use binary search to find
    // smallest K
    while (lo < hi)
    {
        int mi = lo + (hi - lo) / 2;
        if (!isPossible(A, n, H, mi))
            lo = mi + 1;
        else
            hi = mi;
    }
 
    return lo;
}
 
// Driver Code
public static void main(String[] args)
{
    int[] A = { 3, 6, 7, 11 };
    int H = 8;
 
    int n = A.length;
 
    // Print required maxLenwer
    System.out.println(minJobSpeed(A, n, H));
}
}
 
// This code is contributed by mits

// C# program to find minimum speed
// to finish all jobs
  
using System;
using System.Linq;
 
class GFG{
     
// Function to check if the person can do
// all jobs in H hours with speed K
static 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;
}
  
// Function to return the minimum speed
// of person to complete all jobs
static int minJobSpeed(int[] A, int n, int H)
{
    // If H < N it is not possible to complete
    // all jobs as person can not move from
    // one element to another during current hour
    if (H < n)
        return -1;
  
    // Max element of array
    int max = A.Max();
  
    int lo = 1, hi = max;
  
    // Use binary search to find smallest K
    while (lo < hi) {
        int mi = lo + (hi - lo) / 2;
        if (!isPossible(A, n, H, mi))
            lo = mi + 1;
        else
            hi = mi;
    }
  
    return lo;
}
  
// Driver program
public static void Main()
{
    int[] A = { 3, 6, 7, 11 };
    int H = 8;
  
    int n = A.Length;
  
    // Print required maxLenwer
    Console.WriteLine(minJobSpeed(A, n, H));
}
}

# Python3 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
def isPossible(A, n, H, K):
  
    time = 0
   
    for i in range(n):
        time += (A[i] - 1) // K + 1
   
    return time <= H
  
  
# Function to return the minimum speed
# of person to complete all jobs
def minJobSpeed(A, n, H):
  
    # If H < N it is not possible to complete
    # all jobs as person can not move from
    # one element to another during current hour
    if H < n:
        return -1
   
    # Max element of array
    Max = max(A)
   
    lo, hi = 1, Max
   
    # Use binary search to find smallest K
    while lo < hi: 
        mi = lo + (hi - lo) // 2
        if not isPossible(A, n, H, mi):
            lo = mi + 1
        else:
            hi = mi
      
    return lo
  
if __name__ == "__main__": 
 
    A =  [3, 6, 7, 11]
    H = 8
   
    n = len(A)
   
    # Print required maxLenwer
    print(minJobSpeed(A, n, H))
 
# This code is contributed by Rituraj Jain

<script>
 
// Javascript 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 isPossible(A, n, H, K)
{
    var time = 0;
 
    for (var i = 0; i < n; ++i)
        time += parseInt((A[i] - 1) / K) + 1;
 
    return time <= H;
}
 
// Function to return the minimum speed
// of person to complete all jobs
function minJobSpeed(A, n, H)
{
    // If H < N it is not possible to complete
    // all jobs as person can not move from
    // one element to another during current hour
    if (H < n)
        return -1;
 
    // Max element of array
    var max = A.reduce((a,b)=> Math.max(a,b));
 
    var lo = 1, hi = max;
 
    // Use binary search to find smallest K
    while (lo < hi) {
        var mi = lo + parseInt((hi - lo) / 2);
        if (!isPossible(A, n, H, mi))
            lo = mi + 1;
        else
            hi = mi;
    }
 
    return lo;
}
 
// Driver program
var A = [3, 6, 7, 11], H = 8;
var n = A.length;
 
// Print required maxLenwer
document.write( minJobSpeed(A, n, H));
 
// This code is contributed by famously.
</script>

4

Complejidad de tiempo: O(N*log(M)), donde N es la longitud de la array y M es max(A).