logo

TechCodeview

Temps minimum requis pour produire m articles

Donné n machines représentées par un tableau d'entiers arr[] où arr[je] désigne le temps (en secondes) mis par le je-ième machine à produire un article. Toutes les machines fonctionnent simultanément et en continu. De plus, on nous donne également un entier m représentant le nombre total de éléments requis . La tâche consiste à déterminer le temps minimum nécessaire pour produire exactement m articles de manière efficace.

Exemples :  

Saisir: arr[] = [2 4 5] m = 7
Sortir: 8
Explication: La manière optimale de produire 7 articles dans le minimum le temps est 8 secondes. Chaque machine produit des articles à des rythmes différents :



  • Machine 1 produit un article tous les 2 secondes → Produit 8/2 = 4 articles dans 8 secondes.
  • Machine 2 produit un article tous les 4 secondes → Produit 8/4 = 2 articles dans 8 secondes.
  • Machine 3 produit un article tous les 5 secondes → Produit 8/5 = 1 article dans 8 secondes.

Total des articles produits en 8 secondes = 4 + 2 + 1 = 7


Saisir: arr[] = [2 3 5 7] m = 10
Sortir: 9
Explication: La manière optimale de produire 10 articles dans le minimum le temps est 9 secondes. Chaque machine produit des articles à des rythmes différents :

  • La machine 1 produit un article tous les 2 secondes - Produit 9/2 = 4 articles en 9 secondes.
  • La machine 2 produit un article tous les 3 secondes - Produit 9/3 = 3 articles en 9 secondes.
  • La machine 3 produit un article tous les 5 secondes - Produit 9/5 = 1 article en 9 secondes.
  • La machine 4 produit un article tous les 7 secondes - Produit 9/7 = 1 article en 9 secondes.

Total des articles produits en 9 secondes = 4 + 3 + 1 + 1 = 10

Table des matières

Utilisation de la méthode Brute Force - O(n*m*min(arr)) Temps et O(1) Espace

L'idée est de vérifier progressivement le temps minimum requis pour produire exactement m articles. Nous commençons par temps = 1 et continuez à l'augmenter jusqu'à ce que le total des articles produits par toutes les machines ≥m . À chaque pas de temps, nous calculons le nombre d'articles que chaque machine peut produire en utilisant heure / arrivée[i] et résumez-les. Puisque toutes les machines fonctionnent simultanément cette approche garantit que nous trouvons le plus petit temps valide.

C++ 
// C++ program to find minimum time  // required to produce m items using  // Brute Force Approach #include    using namespace std; int minTimeReq(vector<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.size(); 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++;  } } int main() {  vector<int> arr = {2 4 5};  int m = 7;  cout << minTimeReq(arr m) << endl;  return 0; }
Java 
// 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 
# 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# 
// 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 
// 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));

Sortir 
8

Complexité temporelle : O(n*m*min(arr)) car pour chaque unité de temps (jusqu'à m * min(arr)), nous parcourons n machines pour compter les articles produits.
Complexité spatiale : O(1) car seules quelques variables entières sont utilisées ; aucun espace supplémentaire n'est alloué.

Utilisation de la recherche binaire - O(n*log(m*min(arr))) Temps et O(1) Espace

Le idée est d'utiliser Recherche binaire au lieu de vérifier à chaque fois séquentiellement nous observons que le total des articles produits dans un temps donné T peut être calculé en Sur) . L'observation clé est que le temps minimum possible est 1 et le temps maximum possible est m * minMachineTime . En postulant recherche binaire sur cette plage, nous vérifions à plusieurs reprises la valeur moyenne pour déterminer si elle est suffisante et ajustons l'espace de recherche en conséquence.

Étapes pour mettre en œuvre l’idée ci-dessus :

  • Mettre à gauche à 1 et droite à m * minMachineTime pour définir l'espace de recherche.
  • Initialiser ans avec droite pour stocker le temps minimum requis.
  • Exécuter une recherche binaire alors que gauche est inférieur ou égal à droite .
  • Calculer le milieu et calculer le total des éléments en parcourant arr et en résumant milieu / arr[i] .
  • Si totalItems est au moins m mise à jour ans et recherchez un temps plus petit. Sinon ajuster gauche à milieu + 1 pour une durée plus longue.
  • Continuer la recherche jusqu'à ce que le temps minimum optimal soit trouvé.
C++ 
// C++ program to find minimum time  // required to produce m items using  // Binary Search Approach #include    using namespace std; int minTimeReq(vector<int> &arr int m) {    // Find the minimum value in arr manually  int minMachineTime = arr[0];  for (int i = 1; i < arr.size(); 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.size(); 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; } int main() {    vector<int> arr = {2 4 5};  int m = 7;  cout << minTimeReq(arr m) << endl;  return 0; }
Java 
// 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 
# 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# 
// 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 
// 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));

Sortir 
8

Complexité temporelle : O(n log(m*min(arr))) car la recherche binaire exécute log(m × min(arr)) fois chacune en vérifiant n machines.
Complexité spatiale : O(1) car seules quelques variables supplémentaires sont utilisées, ce qui en fait un espace constant.
 

Créer un quiz