logo

TechCodeview

Минимално време, необходимо за производство на m артикула

дадени п машини, представени от масив от цели числа пристигане [] където пристигане[i] обозначава времето (в секунди), заето от i-то машина за производство един елемент. Всички машини работят едновременно и непрекъснато. Освен това ни е дадено и цяло число м представляващи общия брой на необходими елементи . Задачата е да се определи минимално време необходимо за точно производство м елементи ефективно.

Примери:  

вход: arr[] = [2 4 5] m = 7
Изход: 8
Обяснение: Оптималният начин за производство 7 елементи в минимум времето е 8 секунди. Всяка машина произвежда елементи с различна скорост:



  • Машина 1 произвежда артикул всеки 2 секунди → Произвежда 8/2 = 4 елементи в 8 секунди.
  • Машина 2 произвежда артикул всеки 4 секунди → Произвежда 8/4 = 2 елементи в 8 секунди.
  • Машина 3 произвежда артикул всеки 5 секунди → Произвежда 8/5 = 1 т. в 8 секунди.

Общо артикули, произведени в 8 секунди = 4 + 2 + 1 = 7


вход: arr[] = [2 3 5 7] m = 10
Изход: 9
Обяснение: Оптималният начин за производство 10 елементи в минимум времето е 9 секунди. Всяка машина произвежда елементи с различна скорост:

  • Машина 1 произвежда артикул всеки 2 секунди - Произвежда 9/2 = 4 елементи за 9 секунди.
  • Машина 2 произвежда артикул на всеки 3 секунди - Произвежда 9/3 = 3 елементи за 9 секунди.
  • Машина 3 произвежда артикул на всеки 5 секунди - Произвежда 9/5 = 1 артикул за 9 секунди.
  • Машина 4 произвежда артикул всеки 7 секунди - Произвежда 9/7 = 1 артикул за 9 секунди.

Общо артикули, произведени в 9 секунди = 4 + 3 + 1 + 1 = 10

Съдържание

Използване на метода на груба сила - O(n*m*min(arr)) време и O(1) пространство

Идеята е да се постепенна проверка минималното време, необходимо за точно производство м елементи. Започваме с време = 1 и продължете да го увеличавате, докато общите артикули, произведени от всички машини ≥ m . На всяка времева стъпка ние изчисляваме броя елементи, които всяка машина може да произведе, като използва час / пристигане[i] и ги обобщете. Тъй като всички машини работят едновременно този подход гарантира, че намираме най-малкото валидно време.

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

Изход 
8

Времева сложност: O(n*m*min(arr)) тъй като за всяка единица време (до m * min(arr)) ние итерираме през n машини, за да преброим произведените елементи.
Космическа сложност: O(1) тъй като се използват само няколко цели променливи; не се отделя допълнително място.

Използване на двоично търсене - O(n*log(m*min(arr))) време и O(1) пространство

The идея е да се използва Двоично търсене вместо да проверявате всеки път последователно наблюдаваме, че общият брой артикули, произведени за дадено време Т може да се изчисли в O(n) . Основното наблюдение е, че минималното възможно време е 1 а максималното възможно време е m * minMachineTime . Чрез кандидатстване двоично търсене в този диапазон многократно проверяваме средната стойност, за да определим дали е достатъчна и съответно коригираме пространството за търсене.

Стъпки за реализиране на горната идея:

  • Задайте ляво до 1 и точно към m * minMachineTime за определяне на пространството за търсене.
  • Инициализирайте ans с точно за съхраняване на необходимото минимално време.
  • Стартирайте двоично търсене докато наляво е по-малко или равно на точно .
  • Изчислете средата и изчислете totalItems чрез итерация обр и обобщаване среда / пристигане [i] .
  • Ако totalItems е поне m актуализация години и търсене на по-малко време. В противен случай коригирайте наляво към среден + 1 за по-голямо време.
  • Продължете да търсите докато се намери оптималното минимално време.
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));

Изход 
8

Времева сложност: O(n log(m*min(arr))) тъй като двоичното търсене изпълнява log(m × min(arr)) пъти всяка проверка на n машини.
Космическа сложност: O(1) тъй като се използват само няколко допълнителни променливи, което го прави постоянно пространство.
 

Създаване на тест