logo

TechCodeview

Minimale tijd nodig om m artikelen te produceren

Gegeven N machines weergegeven door een integer-array arr[] waar arr[ik] geeft de tijd (in seconden) aan die nodig is voor de i-de machine om te produceren een item. Alle machines werken tegelijkertijd en continu. Daarnaast krijgen we ook een geheel getal M vertegenwoordigt het totale aantal artikelen vereist . De taak is het bepalen van de minimale tijd nodig om precies te produceren M artikelen efficiënt.

Voorbeelden:  

Invoer: arr[] = [2 4 5] m = 7
Uitgang: 8
Uitleg: De optimale manier van produceren 7 artikelen in de minimum tijd is 8 seconden. Elke machine produceert artikelen tegen verschillende tarieven:



  • Machine 1 produceert elke keer een item 2 seconden → Produceert 8/2 = 4 artikelen binnen 8 seconden.
  • Machine 2 produceert elke keer een item 4 seconden → Produceert 8/4 = 2 artikelen binnen 8 seconden.
  • Machine 3 produceert elke keer een item 5 seconden → Produceert 8/5 = 1 artikel binnen 8 seconden.

Totaal aantal artikelen geproduceerd in 8 seconden = 4 + 2 + 1 = 7


Invoer: arr[] = [2 3 5 7] m = 10
Uitgang: 9
Uitleg: De optimale manier van produceren 10 artikelen in de minimum tijd is 9 seconden. Elke machine produceert artikelen tegen verschillende tarieven:

  • Machine 1 produceert elke keer een artikel 2 seconden - Produceert 9/2 = 4 artikelen in 9 seconden.
  • Machine 2 produceert elke keer een artikel 3 seconden - Produceert 9/3 = 3 artikelen in 9 seconden.
  • Machine 3 produceert elke keer een artikel 5 seconden - Produceert 9/5 = 1 artikel in 9 seconden.
  • Machine 4 produceert elke keer een artikel 7 seconden - Produceert 9/7 = 1 artikel in 9 seconden.

Totaal aantal artikelen geproduceerd in 9 seconden = 4 + 3 + 1 + 1 = 10

Inhoudsopgave

Brute Force-methode gebruiken - O(n*m*min(arr)) Tijd en O(1) Ruimte

Het idee is om stapsgewijs controleren de minimale tijd die nodig is om precies te produceren M artikelen. Wij beginnen met tijd = 1 en blijf het verhogen tot het totaal aantal items dat door alle machines is geproduceerd ≥ m . Bij elke tijdstap berekenen we het aantal artikelen waarmee elke machine kan produceren tijd / arr[i] en vat ze samen. Omdat alle machines werken tegelijkertijd deze aanpak zorgt ervoor dat we de kleinste geldige tijd vinden.

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));

Uitvoer 
8

Tijdcomplexiteit: O(n*m*min(arr)) omdat we voor elke tijdseenheid (tot m * min(arr)) door n machines itereren om de geproduceerde items te tellen.
Ruimtecomplexiteit: O(1) omdat er slechts een paar integer-variabelen worden gebruikt; er wordt geen extra ruimte toegewezen.

Binair zoeken gebruiken - O(n*log(m*min(arr))) Tijd en O(1) Ruimte

De idee is te gebruiken Binaire zoekopdracht in plaats van elke keer te controleren opeenvolgend we zien dat het totale aantal items dat in een bepaalde tijd is geproduceerd T kan worden ingerekend Op) . De belangrijkste observatie is dat de minimaal mogelijke tijd dat is 1 en de maximaal mogelijke tijd is m * minMachineTime . Door te solliciteren binaire zoekopdracht binnen dit bereik controleren we herhaaldelijk de middenwaarde om te bepalen of deze voldoende is en passen we de zoekruimte dienovereenkomstig aan.

Stappen om het bovenstaande idee te implementeren:

  • Links ingesteld naar 1 en rechts naar m * minMachineTime om de zoekruimte te definiëren.
  • Initialiseer ant met rechts om de minimaal benodigde tijd op te slaan.
  • Voer een binaire zoekopdracht uit terwijl links kleiner is dan of gelijk is aan rechts .
  • Bereken midden en bereken totalItems door er doorheen te itereren arr en samenvattend midden / arr[i] .
  • Als totalItems minimaal m is update jaar En zoek naar een kleinere tijd. Anders aanpassen links naar midden + 1 voor een grotere tijd.
  • Ga door met zoeken totdat de optimale minimumtijd is gevonden.
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));

Uitvoer 
8

Tijdcomplexiteit: O(n log(m*min(arr))) terwijl Binary Search log(m × min(arr)) maal keer uitvoert en n machines controleert.
Ruimtecomplexiteit: O(1) omdat er slechts een paar extra variabelen worden gebruikt, waardoor er een constante ruimte ontstaat.
 

Quiz maken