Short Problem Definition:
You are planning production for an order. You have a number of machines that each have a fixed number of days to produce an item. Given that all the machines operate simultaneously, determine the minimum number of days to produce the required order.
Link
Complexity:
time complexity is O(N*log(10*9))
space complexity is O(1)
Execution:
This problem statement is a typical binary search challenge. It has a function (the sum of production) that changes in relation to some linear variable (time).
The bounds can be limited by the minimal and maximal production of each machine in the array. This means that the range is 1-10*9, but for most cases, it will be more constrained. It is a big number, but if the function is fast enough, it can be solved in a reasonable time.
There are 10*5 machines, there are completely independent and we have to visit all of them for each iteration. There is no point in memoizing or preprocessing any values, since they change with every iteration.
Hence the time complexity is O(N * log(10*9)).
P.S I always take forever to get binary search right. I should keep a templated (lambda) version of it available, for problems such as this one.
Solution:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#!/bin/pythonimport mathimport osimport randomimport reimport sys# Complete the minTime function below.def minTime(machines, goal): low_bound = goal * min(machines) // len(machines) high_bound = goal * max(machines) // len(machines) + 1 while low_bound < high_bound: days = (low_bound+high_bound) // 2 produced = sum([days // machine for machine in machines]) if produced >= goal: high_bound = days else: low_bound = days + 1 return low_boundif __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') nGoal = raw_input().split() n = int(nGoal[0]) goal = int(nGoal[1]) machines = map(long, raw_input().rstrip().split()) ans = minTime(machines, goal) fptr.write(str(ans) + 'n') fptr.close() |
