Find the Slowest Reading Speed That Still Finishes All Books in Time
Solve this Problempages 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.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of books ≤ 10⁴ - ◆
1 ≤ pages in a single book ≤ 10⁹ - ◆
number of books ≤ hours ≤ 10⁹
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Speed From 1 Upward
BruteReading at speed s, a book with p pages takes ⌈p / s⌉ hours (any leftover pages still cost a full extra hour). Try s = 1, 2, 3, ... and for each one add up the hours every book would take; the first speed whose total fits within the limit is the answer, since a faster speed can only ever need the same or fewer hours than a slower one. Correct, but checking every candidate speed one at a time is wasteful once the page counts get large.
O(n · maxPages)O(1)1class Solution {
2 public int minReadingSpeed(int[] pages, int hours) {
3 int maxPages = 0;
4 for (int p : pages) maxPages = Math.max(maxPages, p);
5 for (int speed = 1; speed <= maxPages; speed++) {
6 long total = 0;
7 for (int p : pages) total += (p + speed - 1) / speed;
8 if (total <= hours) return speed;
9 }
10 return maxPages;
11 }
12}Optimal — Binary Search on the Speed
OptimalThe total hours needed only ever goes down (or stays the same) as the speed goes up — that monotonic relationship is exactly what binary search needs. Search the candidate speeds from 1 to the largest single book: whenever a candidate speed's total hours fits the limit, it's a valid answer, so record it and try a slower (smaller) speed to see if that still works; otherwise the speed is too slow, so search faster.
O(n · log(maxPages))O(1)1class Solution {
2 public int minReadingSpeed(int[] pages, int hours) {
3 int lo = 1, hi = 0;
4 for (int p : pages) hi = Math.max(hi, p);
5 int ans = hi;
6 while (lo <= hi) {
7 int mid = lo + (hi - lo) / 2;
8 long total = 0;
9 for (int p : pages) total += (p + mid - 1) / mid;
10 if (total <= hours) {
11 ans = mid;
12 hi = mid - 1;
13 } else {
14 lo = mid + 1;
15 }
16 }
17 return ans;
18 }
19}