Dado n máquinas representadas por uma matriz inteira arr[] onde arr[eu] denota o tempo (em segundos) gasto pelo eu-ésimo máquina para produzir um item. Todas as máquinas funcionam simultaneamente e continuamente. Além disso, também recebemos um número inteiro eu representando o número total de itens necessários . A tarefa é determinar tempo mínimo necessário para produzir exatamente eu itens de forma eficiente.
Exemplos:
Entrada: arr[] = [2 4 5] m = 7
Saída: 8
Explicação: A maneira ideal de produzir 7 itens no mínimo o tempo é 8 segundos. Cada máquina produz itens em taxas diferentes:
- Máquina 1 produz um item a cada 2 segundos → Produz 8/2 = 4 itens em 8 segundos.
- Máquina 2 produz um item a cada 4 segundos → Produz 8/4 = 2 itens em 8 segundos.
- Máquina 3 produz um item a cada 5 segundos → Produz 8/5 = 1 item em 8 segundos.
Total de itens produzidos em 8 segundos = 4 + 2 + 1 = 7
Entrada: arr[] = [2 3 5 7] m = 10
Saída: 9
Explicação: A maneira ideal de produzir 10 itens no mínimo o tempo é 9 segundos. Cada máquina produz itens em taxas diferentes:
- A máquina 1 produz um item a cada 2 segundos - Produz 9/2 = 4 itens em 9 segundos.
- A máquina 2 produz um item a cada 3 segundos - Produz 9/3 = 3 itens em 9 segundos.
- A máquina 3 produz um item a cada 5 segundos - Produz 9/5 = 1 item em 9 segundos.
- A máquina 4 produz um item a cada 7 segundos - Produz 9/7 = 1 item em 9 segundos.
Total de itens produzidos em 9 segundos = 4 + 3 + 1 + 1 = 10
Índice
- Usando o método de força bruta - O(n*m*min(arr)) Tempo e O(1) Espaço
- Usando pesquisa binária - O(n*log(m*min(arr))) Tempo e O(1) Espaço
Usando o método de força bruta - O(n*m*min(arr)) Tempo e O(1) Espaço
C++A ideia é verificação incremental o tempo mínimo necessário para produzir exatamente eu Unid. Começamos com tempo = 1 e continue aumentando até que o total de itens produzidos por todas as máquinas ≥m . A cada passo de tempo calculamos o número de itens que cada máquina pode produzir usando tempo / chegada[i] e resumi-los. Como todas as máquinas funcionam simultaneamente esta abordagem garante que encontraremos o menor tempo válido.
// C++ program to find minimum time // required to produce m items using // Brute Force Approach #include
// Java program to find minimum time // required to produce m items using // Brute Force Approach import java.util.*; class GfG { static int minTimeReq(int arr[] int m) { // Start checking from time = 1 int time = 1; while (true) { int totalItems = 0; // Calculate total items produced at // current time for (int i = 0; i < arr.length; i++) { totalItems += time / arr[i]; } // If we produce at least m items // return the time if (totalItems >= m) { return time; } // Otherwise increment time and // continue checking time++; } } public static void main(String[] args) { int arr[] = {2 4 5}; int m = 7; System.out.println(minTimeReq(arr m)); } }
# Python program to find minimum time # required to produce m items using # Brute Force Approach def minTimeReq(arr m): # Start checking from time = 1 time = 1 while True: totalItems = 0 # Calculate total items produced at # current time for i in range(len(arr)): totalItems += time // arr[i] # If we produce at least m items # return the time if totalItems >= m: return time # Otherwise increment time and # continue checking time += 1 if __name__ == '__main__': arr = [2 4 5] m = 7 print(minTimeReq(arr m))
// C# program to find minimum time // required to produce m items using // Brute Force Approach using System; class GfG { static int minTimeReq(int[] arr int m) { // Start checking from time = 1 int time = 1; while (true) { int totalItems = 0; // Calculate total items produced at // current time for (int i = 0; i < arr.Length; i++) { totalItems += time / arr[i]; } // If we produce at least m items // return the time if (totalItems >= m) { return time; } // Otherwise increment time and // continue checking time++; } } public static void Main() { int[] arr = {2 4 5}; int m = 7; Console.WriteLine(minTimeReq(arr m)); } }
// JavaScript program to find minimum time // required to produce m items using // Brute Force Approach function minTimeReq(arr m) { // Start checking from time = 1 let time = 1; while (true) { let totalItems = 0; // Calculate total items produced at // current time for (let i = 0; i < arr.length; i++) { totalItems += Math.floor(time / arr[i]); } // If we produce at least m items // return the time if (totalItems >= m) { return time; } // Otherwise increment time and // continue checking time++; } } // Input values let arr = [2 4 5]; let m = 7; console.log(minTimeReq(arr m));
Saída
8
Complexidade de tempo: O(n*m*min(arr)) porque para cada unidade de tempo (até m * min(arr)) iteramos por n máquinas para contar os itens produzidos.
Complexidade Espacial: O(1) já que apenas algumas variáveis inteiras são usadas; nenhum espaço extra é alocado.
Usando pesquisa binária - O(n*log(m*min(arr))) Tempo e O(1) Espaço
O ideia é usar Pesquisa binária em vez de verificar cada vez sequencialmente observamos que o total de itens produzidos em um determinado tempo T pode ser computado em Sobre) . A observação chave é que o tempo mínimo possível é 1 e o tempo máximo possível é m * minMachineTime . Ao aplicar pesquisa binária nesse intervalo, verificamos repetidamente o valor médio para determinar se é suficiente e ajustamos o espaço de pesquisa de acordo.
Passos para implementar a ideia acima:
- Definir à esquerda para 1 e certo para m * minMachineTime para definir o espaço de busca.
- Inicializar e com certo para armazenar o tempo mínimo necessário.
- Execute a pesquisa binária enquanto esquerda é menor ou igual a certo .
- Calcular meio e calcular totalItems iterando através chegar e resumindo meio / arr[i] .
- Se totalItems for pelo menos m atualizar anos e procure por um tempo menor. Caso contrário, ajuste esquerda para meio + 1 por um tempo maior.
- Continuar pesquisando até que o tempo mínimo ideal seja encontrado.
// C++ program to find minimum time // required to produce m items using // Binary Search Approach #include
// Java program to find minimum time // required to produce m items using // Binary Search Approach import java.util.*; class GfG { static int minTimeReq(int[] arr int m) { // Find the minimum value in arr manually int minMachineTime = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] < minMachineTime) { minMachineTime = arr[i]; } } // Define the search space int left = 1; int right = m * minMachineTime; int ans = right; while (left <= right) { // Calculate mid time int mid = left + (right - left) / 2; int totalItems = 0; // Calculate total items produced in 'mid' time for (int i = 0; i < arr.length; i++) { totalItems += mid / arr[i]; } // If we can produce at least m items // update answer if (totalItems >= m) { ans = mid; // Search for smaller time right = mid - 1; } else { // Search in right half left = mid + 1; } } return ans; } public static void main(String[] args) { int[] arr = {2 4 5}; int m = 7; System.out.println(minTimeReq(arr m)); } }
# Python program to find minimum time # required to produce m items using # Binary Search Approach def minTimeReq(arr m): # Find the minimum value in arr manually minMachineTime = arr[0] for i in range(1 len(arr)): if arr[i] < minMachineTime: minMachineTime = arr[i] # Define the search space left = 1 right = m * minMachineTime ans = right while left <= right: # Calculate mid time mid = left + (right - left) // 2 totalItems = 0 # Calculate total items produced in 'mid' time for i in range(len(arr)): totalItems += mid // arr[i] # If we can produce at least m items # update answer if totalItems >= m: ans = mid # Search for smaller time right = mid - 1 else: # Search in right half left = mid + 1 return ans if __name__ == '__main__': arr = [2 4 5] m = 7 print(minTimeReq(arr m))
// C# program to find minimum time // required to produce m items using // Binary Search Approach using System; class GfG { static int minTimeReq(int[] arr int m) { // Find the minimum value in arr manually int minMachineTime = arr[0]; for (int i = 1; i < arr.Length; i++) { if (arr[i] < minMachineTime) { minMachineTime = arr[i]; } } // Define the search space int left = 1; int right = m * minMachineTime; int ans = right; while (left <= right) { // Calculate mid time int mid = left + (right - left) / 2; int totalItems = 0; // Calculate total items produced in 'mid' time for (int i = 0; i < arr.Length; i++) { totalItems += mid / arr[i]; } // If we can produce at least m items // update answer if (totalItems >= m) { ans = mid; // Search for smaller time right = mid - 1; } else { // Search in right half left = mid + 1; } } return ans; } static void Main() { int[] arr = {2 4 5}; int m = 7; Console.WriteLine(minTimeReq(arr m)); } }
// JavaScript program to find minimum time // required to produce m items using // Binary Search Approach function minTimeReq(arr m) { // Find the minimum value in arr manually let minMachineTime = arr[0]; for (let i = 1; i < arr.length; i++) { if (arr[i] < minMachineTime) { minMachineTime = arr[i]; } } // Define the search space let left = 1; let right = m * minMachineTime; let ans = right; while (left <= right) { // Calculate mid time let mid = Math.floor(left + (right - left) / 2); let totalItems = 0; // Calculate total items produced in 'mid' time for (let i = 0; i < arr.length; i++) { totalItems += Math.floor(mid / arr[i]); } // If we can produce at least m items // update answer if (totalItems >= m) { ans = mid; // Search for smaller time right = mid - 1; } else { // Search in right half left = mid + 1; } } return ans; } // Driver code let arr = [2 4 5]; let m = 7; console.log(minTimeReq(arr m));
Saída
8
Complexidade de tempo: O(n log(m*min(arr))) já que a Pesquisa Binária executa log(m × min(arr)) vezes cada verificação de n máquinas.
Complexidade Espacial: O(1) já que apenas algumas variáveis extras são usadas, tornando-o um espaço constante.