AceYourInterviews
Checking sign-in…

66. Koko Eating Bananas — Minimum Feasible Rate

CoreFirst feasible rate under a ceiling-sum budget

Choose one fixed eating rate. During an hour, work on at most one pile; finishing that pile early does not allow using the remaining fraction of the hour on another pile.

Find the minimum rate that finishes all piles within the time allowance. The contract defines feasibility and the zero result for an empty pile collection.

Example 1

Input

piles=[3,6,7,11], hours=8

Output

4

Explanation: At rate 4, hours per pile are [1,2,2,3], totaling 8; rate 3 needs 10.

Example 2

Input

piles=[30,11,23,4,20], hours=5

Output

30

Explanation: Only one hour per pile is available, forcing the largest pile to fit in one hour.

Example 3

Input

piles=[MAX], hours=2

Output

1,073,741,824

Explanation: ceil(MAX/2) rate is computed without an overflowing pile+rate−1 int expression.

Example 4

Input

piles=[], hours=0

Output

0

Explanation: The explicitly empty workload has no positive-rate requirement.

Constraints

  • 0 <= piles.length <= 105
  • 1 <= piles[i] <= 231 - 1
  • piles.length <= hours <= 263 - 1
Hints
Hint 1

For a candidate rate, exactly how many hours does each pile consume independently?

Hint 2

Why does increasing the rate preserve every feasible budget?

Hint 3

Validate H>=n, search [1,max pile], retain feasible midpoints, and use widened integer ceilings.

Practice on LeetCode ↗
Code
Saved on this deviceLn 1, Col 1

Ceiling hours determine the first feasible rate

[3,6,7,11]
8
4