Donat n màquines representades per una matriu enter arr[] on arr[i] indica el temps (en segons) que triga el i-è màquina per produir un element. Totes les màquines funcionen simultàniament i contínuament. A més, també se'ns dóna un nombre enter m que representa el nombre total de elements requerits . La tasca és determinar el temps mínim necessari per produir exactament m articles de manera eficient.
Exemples:
Entrada: arr[] = [2 4 5] m = 7
Sortida: 8
Explicació: La manera òptima de produir 7 elements a la mínim el temps és 8 segons. Cada màquina produeix articles a diferents ritmes:
- Màquina 1 produeix un article cada 2 segons → Produeix 8/2 = 4 articles en 8 segons.
- Màquina 2 produeix un article cada 4 segons → Produeix 8/4 = 2 articles en 8 segons.
- Màquina 3 produeix un article cada 5 segons → Produeix 8/5 = 1 element dins 8 segons.
Total d'articles produïts a 8 segons = 4 + 2 + 1 = 7
Entrada: arr[] = [2 3 5 7] m = 10
Sortida: 9
Explicació: La manera òptima de produir 10 elements a la mínim el temps és 9 segons. Cada màquina produeix articles a diferents ritmes:
- La màquina 1 produeix un article cada 2 segons - Produeix 9/2 = 4 elements en 9 segons.
- La màquina 2 produeix un article cada 3 segons - Produeix 9/3 = 3 elements en 9 segons.
- La màquina 3 produeix un article cada 5 segons - Produeix 9/5 = 1 element en 9 segons.
- La màquina 4 produeix un article cada 7 segons - Produeix 9/7 = 1 element en 9 segons.
Total d'articles produïts a 9 segons = 4 + 3 + 1 + 1 = 10
Taula de continguts
- Ús del mètode de força bruta - O(n*m*min(arr)) Temps i O (1) Espai
- Ús de la cerca binària - O(n*log(m*min(arr))) Temps i O(1) Espai
Ús del mètode de força bruta - O(n*m*min(arr)) Temps i O (1) Espai
C++La idea és fer comprovar gradualment el temps mínim necessari per produir exactament m elements. Comencem amb temps = 1 i seguir augmentant-lo fins al total d'articles produïts per totes les màquines ≥ m . En cada pas de temps calculem el nombre d'articles que cada màquina pot produir utilitzant hora/arr[i] i resumir-los. Ja que totes les màquines funcionen simultàniament aquest enfocament garanteix que trobem el temps vàlid més petit.
// 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));
Sortida
8
Complexitat temporal: O(n*m*min(arr)) perquè per a cada unitat de temps (fins a m * min(arr)) iterem a través de n màquines per comptar els articles produïts.
Complexitat espacial: O(1) ja que només s'utilitzen poques variables senceres; no s'assigna espai addicional.
Ús de la cerca binària - O(n*log(m*min(arr))) Temps i O(1) Espai
El idea és utilitzar Cerca binària en lloc de comprovar cada cop seqüencialment observem que el total d'articles produïts en un temps determinat T es pot calcular en O(n) . L'observació clau és que el temps mínim possible és 1 i el temps màxim possible és m * minMachineTime . Mitjançant la sol·licitud cerca binària en aquest rang, comprovem repetidament el valor mitjà per determinar si és suficient i ajustem l'espai de cerca en conseqüència.
Passos per implementar la idea anterior:
- Posa a l'esquerra a 1 i dret a m * minMachineTime per definir l'espai de cerca.
- Inicialitzar ans amb dret per emmagatzemar el temps mínim necessari.
- Executeu la cerca binària mentre esquerra és menor o igual a dret .
- Calcular mig i calculeu totalItems iterant arr i resumint mig/arr[i] .
- Si totalItems és com a mínim m actualitzar anys i buscar un temps més petit. En cas contrari ajustar esquerra a mig + 1 per un temps més gran.
- Continuar cercant fins que es trobi el temps mínim òptim.
// 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));
Sortida
8
Complexitat temporal: O(n log(m*min(arr))) ja que la cerca binària executa log(m × min(arr)) vegades cada comprovació de n màquines.
Complexitat espacial: O(1) ja que només s'utilitzen unes poques variables addicionals fent-lo espai constant.