There are N workers in a factory. Each worker packs the same type of product, and for each of them we know the time it takes them to pack one product.
Find out the minimum amount of time the workers need to pack at least K products.
Example:
Input: times = [4, 7, 3, 6, 7, 1], K = 60
Output:30
Explanation:
1st worker packs 7 products in 4 * 7 = 28 units of time
2nd worker packs 4 products in 7 * 4 = 28 units of time
3rd worker packs 10 products in 3 * 10 = 30 units of time
4th worker packs 5 products in 6 * 5 = 30 units of time
5th worker packs 4 products in 7 * 4 = 28 units of time
6th worker packs 30 products in 1 * 30 = 30 units of time
We have 7 + 4 + 10 + 5 + 4 + 30 = 60 total products
in max(28, 28, 30, 30, 28, 30) = 30 units of time
and this is the minimum amount of time
since in 29 units of time we can pack only
7 + 4 + 9 + 4 + 4 + 29 = 57 products
Note:
Your algorithm should run in O(n * log(k * T)) time and use O(1) extra space.
Walkthroughs of the solution. Try the steps first, then watch to compare approaches.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check