Find the Slowest Reading Speed That Still Finishes All Books in Time
Implement minReadingSpeed
Given an array
pages where each value is the number of pages in one book, and an integer hours, find the slowest possible reading speed (in whole pages per hour) that still finishes every book within the time limit.
You read one book at a time, always at the same constant integer speed. A book with p pages, read at speed s, takes ⌈p / s⌉ hours — even one leftover page still costs a full extra hour, since you can't carry unfinished pages into the next book's count. Return the minimum integer speed that keeps the total hours across every book at or under hours — a solution is always guaranteed to exist as long as there are at least as many hours as books.
The total hours needed only ever decreases (or stays flat) as the reading speed increases, which makes this a binary search on the answerBinary Search on the AnswerInstead of searching a sorted array, the search runs directly over the space of possible answers (here, every candidate reading speed). It works whenever "is this candidate good enough?" is monotonic — once a candidate works, every larger (or smaller, depending on direction) candidate keeps working too. — search directly over candidate speeds rather than over the books themselves.
Example 1:
Input: pages = [12,20,17,9], hours = 10
Output: 7
Example 2:
Input: pages = [7], hours = 3
Output: 3
Example 3:
Input: pages = [25,14,33,8,19], hours = 12
Output: 10
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ number of books ≤ 10⁴ - ●
1 ≤ pages in a single book ≤ 10⁹ - ●
number of books ≤ hours ≤ 10⁹
pages =
[12, 20, 17, 9]
hours =
10