362. Store Shelving
A distributor owns stores shops and several types of product. The array quantities says how many items of each product type there are. Every item must be shelved, and a store may hold items of only one product type (although one product type may be spread over several stores).
The distributor wants to shelve everything so that the busiest store holds as few items as possible. Return the smallest possible value of the largest number of items in any store. You may assume that stores is at least the number of product types, so a valid arrangement always exists.
Example 1
- Input:
- stores = 5, quantities = [11,6]
- Output:
- 4
- Explanation:
Put 11 items as 4 + 4 + 3 in three stores and 6 items as 3 + 3 in two stores; the largest store has 4 items.
Example 2
- Input:
- stores = 3, quantities = [7,7,7]
- Output:
- 7
- Explanation:
Each product type gets one store with 7 items, so the answer is 7.
Constraints
1 ≤ quantities.length ≤ stores ≤ 105
1 ≤ quantities[i] ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(m log M)
- Space
- O(1)