Tiempo mínimo para completar al menos K tareas cuando todos descansan después de cada tarea

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N que representa el tiempo que tarda una persona en completar una tarea. Además, una array restTime[] que denota la cantidad de tiempo que una persona tarda en descansar después de terminar una tarea. Cada persona es independiente de los demás, es decir, pueden trabajar simultáneamente en diferentes tareas al mismo tiempo. Dado un número entero K , la tarea consiste en encontrar al menos cuánto tiempo tardarán todas las personas en completar todas las tareas K.

Ejemplos:

Entrada: arr[] = {1, 2, 4}, restTime[] = {1, 2, 2}, K = 5 Salida: 5
Explicación :
En t = 1, tareas tarea realizada = [1, 0, 0] , Tarea total = 1
En t = 2, Número de tareas completadas = [1, 1, 0],  
Tarea total = 1 + 1 = 2. Debido a que la primera persona estaba descansando
En t = 3, Número de tareas completadas = [2 , 1, 0],  
tarea total = 2 + 1 = 3, porque la segunda persona estaba descansando
en t = 4, número de tareas completadas = [2, 1, 1],  
tarea total = 2 + 1 + 1 = 4, Debido a que la primera y la segunda persona estaban descansando
en t = 5, número de tareas completadas = [3, 1, 1]. 
Tarea total = 3 + 1 + 1 = 5. Tiempo mínimo empleado = 5.

Entrada: arr[] = {1, 2, 4, 7, 8}, restTime[] = {4, 1, 2, 3, 1}, TotalTask ​​= 2 Salida
: 2

 

Enfoque: El problema se puede resolver usando Binary Search , basado en las siguientes observaciones:

El tiempo mínimo necesario puede ser 1 y el tiempo máximo necesario puede ser muy grande. Si en un tiempo x se pueden completar todas las tareas K , entonces también es posible que se puedan completar en menos de un tiempo x . Utilice este concepto para aplicar la búsqueda binaria en el tiempo requerido. 

Siga los pasos a continuación para implementar el enfoque anterior:

  • Cree una variable st = 1, represente el punto inicial del rango de tiempo y end = INT_MAX, el punto final.
  • Use la búsqueda binaria en el rango de st a end :
    • Calcular mid = st + (end – st)/2
    • Compruebe si las tareas K se pueden completar en la mitad de la cantidad de tiempo:
      • Si se puede completar, establezca end = mid-1.
      • De lo contrario, establezca st = mid+1.
  • Regresar st al final ya que este será el tiempo mínimo requerido.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it is possible
// to complete atleast totaltask using
// current mid total time
bool timePossible(int mid, int totalTask,
                  vector<int>& timeArr,
                  vector<int>& restTime)
{
    // Variable to store total task
    int curTask = 0;
 
    // Loop to check if it is possible
    // to complete totalTask in mid time
    for (int i = 0; i < timeArr.size(); i++) {
        int totalTime
            = timeArr[i] + restTime[i];
        curTask += mid / totalTime;
        if (mid % totalTime >= timeArr[i])
            curTask++;
 
        // Possible condition
        if (curTask >= totalTask) {
            return true;
        }
    }
 
    // If possible print true
    if (curTask >= totalTask) {
        return true;
    }
 
    // Else return false
    return false;
}
 
// Function to find minimum time taken
int minimumTimeTaken(vector<int>& timeArr,
                     vector<int>& restTime,
                     int totalTask)
{
    // The ranges of time
    int st = 1;
    int end = INT_MAX;
 
    // Variable to store minimum time
    int minimumtime = 0;
 
    while (st <= end) {
        int mid = st + (end - st) / 2;
 
        // If this mid value is possible
        // try to minimise it
        if (timePossible(mid, totalTask,
                         timeArr, restTime))
            end = mid - 1;
        else
            st = mid + 1;
    }
 
    // Print the minimum time as answer
    return st;
}
 
// Driver code
int main()
{
    vector<int> arr = { 1, 2, 4 };
    vector<int> restTime = { 1, 2, 2 };
    int K = 5;
 
    // Function call
    cout << minimumTimeTaken(arr,
                             restTime, K);
    return 0;
}

Java

// Java code for the above approach
import java.io.*;
 
class GFG
{
   
  // Function to check if it is possible
  // to complete atleast totaltask using
  // current mid total time
  public static boolean timePossible(int mid,
                                     int totalTask,
                                     int timeArr[],
                                     int restTime[])
  {
    // Variable to store total task
    int curTask = 0;
 
    // Loop to check if it is possible
    // to complete totalTask in mid time
    for (int i = 0; i < timeArr.length; i++) {
      int totalTime = timeArr[i] + restTime[i];
      curTask += mid / totalTime;
      if (mid % totalTime >= timeArr[i])
        curTask++;
 
      // Possible condition
      if (curTask >= totalTask) {
        return true;
      }
    }
 
    // If possible print true
    if (curTask >= totalTask) {
      return true;
    }
 
    // Else return false
    return false;
  }
 
  // Function to find minimum time taken
  public static int minimumTimeTaken(int timeArr[],
                                     int restTime[],
                                     int totalTask)
  {
    // The ranges of time
    int st = 1;
    int end = Integer.MAX_VALUE;
 
    // Variable to store minimum time
    int minimumtime = 0;
 
    while (st <= end) {
      int mid = st + (end - st) / 2;
 
      // If this mid value is possible
      // try to minimise it
      if (timePossible(mid, totalTask, timeArr,
                       restTime)
          != false)
        end = mid - 1;
      else
        st = mid + 1;
    }
 
    // Print the minimum time as answer
    return st;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int arr[] = { 1, 2, 4 };
    int restTime[] = { 1, 2, 2 };
    int K = 5;
 
    // Function call
    System.out.print(
      minimumTimeTaken(arr, restTime, K));
  }
}
 
// This code is contributed by Rohit Pradhan

Python3

# python3 code for the above approach
 
INT_MAX = 2147483647
 
# Function to check if it is possible
# to complete atleast totaltask using
# current mid total time
 
 
def timePossible(mid, totalTask, timeArr, restTime):
 
    # Variable to store total task
    curTask = 0
 
    # Loop to check if it is possible
    # to complete totalTask in mid time
    for i in range(0, len(timeArr)):
        totalTime = timeArr[i] + restTime[i]
        curTask += mid // totalTime
        if (mid % totalTime >= timeArr[i]):
            curTask += 1
 
        # Possible condition
        if (curTask >= totalTask):
            return True
 
    # If possible print true
    if (curTask >= totalTask):
        return True
 
    # Else return false
    return False
 
 
# Function to find minimum time taken
def minimumTimeTaken(timeArr, restTime, totalTask):
 
    # The ranges of time
    st = 1
    end = INT_MAX
 
    # Variable to store minimum time
    minimumtime = 0
 
    while (st <= end):
        mid = st + (end - st) // 2
 
        # If this mid value is possible
        # try to minimise it
        if (timePossible(mid, totalTask,
                         timeArr, restTime)):
            end = mid - 1
        else:
            st = mid + 1
 
    # Print the minimum time as answer
    return st
 
 
# Driver code
if __name__ == "__main__":
 
    arr = [1, 2, 4]
    restTime = [1, 2, 2]
    K = 5
 
    # Function call
    print(minimumTimeTaken(arr, restTime, K))
 
    # This code is contributed by rakeshsahni

C#

// C# program for above approach
using System;
class GFG
{
 
  // Function to check if it is possible
  // to complete atleast totaltask using
  // current mid total time
  public static bool timePossible(int mid,
                                  int totalTask,
                                  int[] timeArr,
                                  int[] restTime)
  {
    // Variable to store total task
    int curTask = 0;
 
    // Loop to check if it is possible
    // to complete totalTask in mid time
    for (int i = 0; i < timeArr.Length; i++) {
      int totalTime = timeArr[i] + restTime[i];
      curTask += mid / totalTime;
      if (mid % totalTime >= timeArr[i])
        curTask++;
 
      // Possible condition
      if (curTask >= totalTask) {
        return true;
      }
    }
 
    // If possible print true
    if (curTask >= totalTask) {
      return true;
    }
 
    // Else return false
    return false;
  }
 
  // Function to find minimum time taken
  public static int minimumTimeTaken(int[] timeArr,
                                     int[] restTime,
                                     int totalTask)
  {
    // The ranges of time
    int st = 1;
    int end = Int32.MaxValue;
 
    // Variable to store minimum time
    int minimumtime = 0;
 
    while (st <= end) {
      int mid = st + (end - st) / 2;
 
      // If this mid value is possible
      // try to minimise it
      if (timePossible(mid, totalTask, timeArr,
                       restTime)
          != false)
        end = mid - 1;
      else
        st = mid + 1;
    }
 
    // Print the minimum time as answer
    return st;
  }
 
  // Driver Code
  public static void Main()
  {
    int[] arr = { 1, 2, 4 };
    int[] restTime = { 1, 2, 2 };
    int K = 5;
 
    // Function call
    Console.Write(
      minimumTimeTaken(arr, restTime, K));
  }
}
 
// This code is contributed by code_hunt.

Javascript

<script>
 
// JavaScript code for the above approach
 
// Function to check if it is possible
// to complete atleast totaltask using
// current mid total time
function timePossible(mid, totalTask, timeArr, restTime)
{
 
    // Variable to store total task
    let curTask = 0;
 
    // Loop to check if it is possible
    // to complete totalTask in mid time
    for (let i = 0; i < timeArr.length; i++)
    {
        let totalTime = timeArr[i] + restTime[i];
        curTask += Math.floor(mid / totalTime);
        if (mid % totalTime >= timeArr[i])
            curTask++;
 
        // Possible condition
        if (curTask >= totalTask) {
            return true;
        }
    }
 
    // If possible print true
    if (curTask >= totalTask) {
        return true;
    }
 
    // Else return false
    return false;
}
 
// Function to find minimum time taken
function minimumTimeTaken(timeArr, restTime, totalTask)
{
 
    // The ranges of time
    let st = 1;
    let end = Number.MAX_VALUE;
 
    // Variable to store minimum time
    let minimumtime = 0;
 
    while (st <= end) {
        let mid = st + Math.floor((end - st) / 2);
 
        // If this mid value is possible
        // try to minimise it
        if (timePossible(mid, totalTask,
                         timeArr, restTime))
            end = mid - 1;
        else
            st = mid + 1;
    }
 
    // Print the minimum time as answer
    return st;
}
 
// Driver code
let arr = [ 1, 2, 4 ];
let restTime = [ 1, 2, 2 ];
let K = 5;
 
// Function call
document.write(minimumTimeTaken(arr, restTime, K));
 
// This code is contributed by shinjanpatra
 
</script>
Producción

5

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por geekyss y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *