Last Updated: 31 Mar, 2025
Simultaneous Production
Easy
Asked in company
You are given the number of machines 'N', an array 'M' of length 'N' where 'M[i]' represents the number of days the i-th machine takes to produce one item, and the total number of items 'O' that need to be ordered.
Return the minimum number of days required for all machines working in parallel to complete the order.
For Example :
Let 'N' = 2, 'M' = [3, 1], 'O' = 5.
Day 1: Machine 2 produces an item
Day 2: Machine 2 produces an item
Day 3: Both Machine 1 and Machine 2 produce an item
Day 4: Machine 2 produces an item
Total items produced = 1 + 1 + 2 + 1 = 5 items.
Therefore, the answer is 4 days.
Input Format :
The first line contains three integers, 'N', 'O'.
The second line contains 'N' integers representing the array 'M'.
Output Format :
Return the minimum number of days required to complete the order.
Note :
You don’t need to print anything. Just implement the given function.
Constraints :
1 <= 'N' <= 10^5
1 <= 'M[i]' <= 10^9
1 <= 'O' <= 10^9
Time Limit: 1 sec
Approaches
Approach:
- We can perform a binary search on the number of days.
- The lower bound for the number of days can be 0 (although practically it will be 1)
- The upper bound can be the maximum production time multiplied by the total number of items.
- For a given number of days 'D', we can calculate the total number of items that can be produced by all machines working in parallel.
- For each machine 'i', the number of items it can produce in 'D' days is 'D / M[i]' (integer division).
- We sum up the number of items produced by all machines.
- If the total number of items produced is greater than or equal to the required order 'O', it means that the order can be completed in 'D' days or less.
- So, we try a smaller number of days in the binary search.
- If the total number of items produced is less than 'O', it means that 'D' days are not enough
- So, we need to try a larger number of days.
- If the total number of items produced is greater than or equal to the required order 'O', it means that the order can be completed in 'D' days or less.
- We continue the binary search until the lower bound and upper bound converge to the minimum number of days.
Algorithm:
- Initialize 'low' to 1.
- Initialize 'high' to max(M) * O.
- Initialize 'ans' to 'high'.
- While 'low' is less than or equal to 'high':
- Calculate 'mid' as (low + high) // 2.
- Initialize 'total_produced' to 0.
- Iterate through each machine's production time 'time' in 'M':
- Add mid // time to 'total_produced'.
- If 'total_produced' is greater than or equal to 'O':
- Set 'ans' to 'mid'.
- Set 'high' to mid - 1.
- Else:
- Set 'low' to mid + 1.
- Return 'ans'.
Similar problems