352. Snack Speed
A hungry visitor at a buffet faces piles of snacks, piles[i] snacks in the i-th pile. Each hour she picks one pile and eats up to k snacks from it. If the pile has fewer than k snacks she finishes it and does nothing else that hour.
She must finish every pile within h hours, where h is at least the number of piles. Return the smallest whole number k of snacks per hour that lets her finish in time. The numbers are large, so trying every k is far too slow.
Example 1
- Input:
- piles = [12,4,9,20], h = 7
- Output:
- 9
- Explanation:
At 8 snacks per hour she needs 2 + 1 + 2 + 3 = 8 hours, which is too many; at 9 per hour she needs 2 + 1 + 1 + 3 = 7 hours, so 9 is the smallest speed that works.
Example 2
- Input:
- piles = [6,6], h = 2
- Output:
- 6
- Explanation:
Each pile needs one hour only if she can eat 6 in an hour, so k = 6.
Constraints
1 ≤ piles.length ≤ 105
piles.length ≤ h ≤ 109
1 ≤ piles[i] ≤ 109
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(n log M), where M is the largest pile
- Space
- O(1)