875. Koko Eating Bananas
Tags:
Medium
Skills:
Binary Search
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm tốc độ ăn tối thiểu k (số lượng chuối ăn mỗi giờ) để Koko có thể ăn hết tất cả các đống chuối trong h giờ
Approach
- Xác định phạm vi bài toán
- Tốc độ ăn tối thiểu k là 1 (Koko ăn ít nhất 1 chuỗi mỗi giờ)
- Tốc độ ăn tối đa k là số lượng chuối lớn nhất trong một đống (vì nếu Koko ăn nhanh hơn thì không cần thiết)
- Kiểm tra tính khả thi của một tốc độ k
- Với một tốc độ k, tính tổng số giờ cần thiết để Koko ăn hết tất cả đống chuối
- Neues hoursTaken ≤ h, thì tốc độ k là khả thi
- Sử dụng Binary Search
- Dùng Binary Search để tìm giá trị nhỏ nhất của k mà vẫn thỏa mãn điều kiện hoursTaken ≤ h
- Nếu tốc độ hiện tại khả thi (hoursTaken ≤ h), giảm phạm vi tìm kiếm bằng cách đặt end = mid - 1
- Nếu tốc độ hiện tại không khả thi (hoursTaken > h), tăng phạm vi tìm kiếm bằng cách đặt start = mid - 1
Solution - Binary Search
typescripttypescript
1function minEatingSpeed(piles: number[], h: number): number {
2 function canEatAll(k: number): boolean {
3 let hours_taken = 0;
4 for (const pile of piles) {
5 hours_taken += Math.ceil(pile / k);
6 }
7
8 if (hours_taken > h) {
9 return false;
10 }
11
12 return hours_taken <= h
13 }
14
15 let left = 0;
16 let right = Math.max(...piles);
17 while (left <= right) {
18 const mid = left + Math.floor((right - left) / 2);
19 if (canEatAll(mid)) {
20 right = mid - 1
21 } else {
22 left = mid + 1
23 }
24 }
25
26 return left;
27};