Start learning free

LESSON 382 OF 677 · BINARY SEARCH

The Factory

Practice O(n * k * T)

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 * K * T) time, where T is the smallest value in times, and use O(1) extra space.


STEP 1 OF 9
    Ctrl + Enter to check