eating.py (1039B)
1 import math 2 3 4 class Solution: 5 6 # IDEA: 7 8 # Brute force: 9 # Check all values for k, starting from 1 to m := max(piles) 10 # and return smallest value 11 12 # Optimized approach: 13 # we can use a binary search from 1 to m, 14 # checking at each step if k is sufficient 15 # to solve the problem. 16 # If k solves the problem, check lower values 17 # If it doesn't, check higher values. 18 19 def minEatingSpeed(self, piles: List[int], h: int) -> int: 20 21 m = max(piles) 22 23 lower = 1 24 upper = m 25 26 smallest_k = upper 27 while lower <= upper: 28 29 center = ((upper - lower) // 2) + lower 30 31 if possible(piles, h, center): 32 smallest_k = center 33 upper = center - 1 34 else: 35 lower = center + 1 36 37 return smallest_k 38 39 40 # h = hours 41 # k = bph 42 def possible(piles, h, k): 43 44 total_hours = 0 45 for pile in piles: 46 total_hours += math.ceil(pile / k) 47 if total_hours > h: 48 return False 49 50 return True