Binary Search trên đáp án: Tốc độ ăn chuối của Koko và một pattern lớn hơn

Koko có n đống chuối và h giờ trước khi lính canh quay lại. Cô chọn tốc độ ăn k (chuối mỗi giờ), và mỗi giờ cô ăn tối đa k quả từ đúng một đống. Cô muốn tốc độ nhỏ nhất để ăn hết tất cả kịp giờ. Nhiệm vụ của bạn là tìm k đó.

Nhìn lần đầu trông giống bài simulation. Thử từng tốc độ, kiểm tra từng cái. Nhưng observation then chốt là feasibility là monotonic: nếu tốc độ k đủ thì k+1 cũng đủ. Tính monotonic đó có nghĩa là bạn không tìm kiếm một target trong mảng — bạn tìm điểm đầu tiên trong không gian giá trị mà predicate chuyển từ false sang true. Binary search áp dụng, và áp dụng rất sạch.

Đề bài

Cho n đống chuối và h giờ cho đến khi lính canh quay về, tìm số nguyên tốc độ ăn nhỏ nhất k để Koko ăn hết tất cả các đống trong h giờ, mỗi giờ ăn tối đa k quả từ một đống. Đề bài đầy đủ: LeetCode 875.

Ràng buộc:
- 1 <= piles.length <= 10^4
- piles.length <= h <= 10^9
- 1 <= piles[i] <= 10^9

Constraints ép buộc gì

Đọc constraints trước khi viết một dòng code:

• 1 <= piles.length <= 10^4 — tối đa mười nghìn đống
• piles.length <= h <= 10^9 — số giờ có thể cực kỳ lớn
• 1 <= piles[i] <= 10^9 — mỗi đống có thể lên đến một tỷ quả

Giới hạn h chỉ ảnh hưởng đến mức độ khoan nhượng của feasibility check chứ không ảnh hưởng đến algorithm. Nhưng piles[i] lên đến 10^9 mới là thứ giết chết brute force. Không gian tìm kiếm cho k chạy từ 1 đến max(piles), có thể là 10^9. Quét từng candidate tuyến tính là O(max(piles) * n) — lên đến 10^13 operations. Không cách nào pass được.

n <= 10^4 với log(10^9) ~= 30 iterations binary search cho 10^4 * 30 = 3 * 10^5 operations cho mỗi validation — trong giới hạn thời gian một cách thoải mái. Constraints này gần như la to "binary search trên không gian giá trị."

Cận dưới của tìm kiếm là 1 (Koko ăn ít nhất một quả mỗi giờ; bài đảm bảo piles[i] >= 1). Cận trên là max(piles): ở tốc độ đó cô ăn hết mỗi đống trong đúng một giờ, n đống mất n giờ, và vì h >= n nên cái này luôn đúng.

Brute force: quét từng tốc độ candidate

Cách tiếp cận thẳng thắn: thử mọi số nguyên từ 1 đến max(piles), trả về cái đầu tiên pass feasibility check.

import math
 
class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        def can_finish(k: int) -> bool:
            total = 0
            for pile in piles:
                total += math.ceil(pile / k)
            return total <= h
 
        for k in range(1, max(piles) + 1):
            if can_finish(k):
                return k
 
        return max(piles)  # không bao giờ đến đây với constraints hợp lệ

using System;
using System.Linq;
 
public class Solution {
    public int MinEatingSpeed(int[] piles, int h) {
        bool CanFinish(int k) {
            long total = 0;
            foreach (int pile in piles) {
                total += (pile + k - 1) / k;  // ceiling không dùng floating point
            }
            return total <= h;
        }
 
        int maxPile = piles.Max();
        for (int k = 1; k <= maxPile; k++) {
            if (CanFinish(k)) return k;
        }
 
        return maxPile;
    }
}

Trick ceiling division (pile + k - 1) / k quan trọng trong C#: integer division truncate, nên không thể viết pile / k mà mong nó ra ceiling. Trong Python, math.ceil(pile / k) hoạt động nhưng chuyển sang float; (pile + k - 1) // k là dạng portable nhất.

Complexity: O(max(piles) * n) time, O(1) space. Với max(piles) = 10^9 và n = 10^4, cái này TLE ngay trên bất kỳ input nào không phải đồ chơi.

Binary search trên hàm feasibility

Insight then chốt: can_finish(k) là false với k nhỏ và true với k lớn, với đúng một điểm chuyển tiếp. Binary search tìm điểm đó trong O(log(max(piles))) lần gọi can_finish thay vì O(max(piles)) lần.

Template ở đây là "tìm vị trí trái nhất mà predicate trở thành true." Chúng ta duy trì left và right sao cho đáp án luôn nằm trong [left, right], và thu hẹp interval cho đến khi left == right.

import math
 
class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        def can_finish(k: int) -> bool:
            total = 0
            for pile in piles:
                total += math.ceil(pile / k)
                if total > h:  # early exit: đã vượt budget
                    return False
            return True
 
        left, right = 1, max(piles)
 
        while left < right:
            mid = (left + right) // 2
            if can_finish(mid):
                right = mid       # mid được, nhưng có thể có cái nhỏ hơn
            else:
                left = mid + 1    # mid không được, cần nhiều hơn
 
        return left

using System;
using System.Linq;
 
public class Solution {
    public int MinEatingSpeed(int[] piles, int h) {
        bool CanFinish(int k) {
            long total = 0;
            foreach (int pile in piles) {
                total += (pile + k - 1) / k;
                if (total > h) return false;  // early exit
            }
            return true;
        }
 
        int left = 1;
        int right = piles.Max();
 
        while (left < right) {
            int mid = left + (right - left) / 2;  // tránh overflow so với (left+right)/2
            if (CanFinish(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
 
        return left;
    }
}

Hai chi tiết đáng chú ý. Thứ nhất, mid = left + (right - left) / 2 thay vì (left + right) / 2 — trong C# (và Java), left + right có thể overflow nếu cả hai gần int.MaxValue. Python integers không overflow, nhưng dạng an toàn này vẫn dễ đọc như nhau. Thứ hai, early exit trong can_finish là constant-factor optimization: khi running sum vượt h, chúng ta biết kết quả mà không cần duyệt qua các piles còn lại.

Complexity: O(n * log(max(piles))) time, O(1) space. Với giới hạn đã cho, khoảng 10^4 * 30 = 3 * 10^5 operations.

Trace tay qua Example 1

piles = [3, 6, 7, 11], h = 8. Vậy left = 1, right = 11.

Từng bước:

• mid = 6: số giờ cần là ceil(3/6) + ceil(6/6) + ceil(7/6) + ceil(11/6) = 1 + 1 + 2 + 2 = 6. Sáu nhỏ hơn hoặc bằng 8, vậy 6 được. Nhưng có thể cái nhỏ hơn cũng được. Đặt right = 6.
• mid = 3: số giờ là ceil(3/3) + ceil(6/3) + ceil(7/3) + ceil(11/3) = 1 + 2 + 3 + 4 = 10. Mười vượt quá 8, tốc độ 3 không đủ. Đặt left = 4.
• mid = 5: số giờ là 1 + 2 + 2 + 3 = 8. Đúng bằng 8, nhỏ hơn hoặc bằng h. Đặt right = 5.
• mid = 4: số giờ là ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8. Vẫn được. Đặt right = 4.
• left == right == 4. Return 4.

Thời điểm then chốt là bước thứ ba: tốc độ 4 và tốc độ 5 đều hoàn thành trong đúng 8 giờ. Binary search tự nhiên chọn cái nhỏ hơn vì mỗi khi can_finish trả về true, chúng ta kéo right xuống thay vì chấp nhận mid là đáp án ngay lập tức.

Các edge case thực sự quan trọng

h == piles.length (đúng một giờ mỗi đống): Koko không có thời gian dư thừa. Cô phải ăn hết đống lớn nhất trong một giờ, vậy k = max(piles). Binary search đến được đây: can_finish(max(piles) - 1) sẽ trả về false vì ít nhất đống lớn nhất cần 2 giờ ở tốc độ đó.

Một đống duy nhất (n = 1): Tìm kiếm chạy từ 1 đến piles[0], và đáp án là ceil(piles[0] / h). Binary search tìm đúng cái này; không cần special case.

h rất lớn (lớn hơn nhiều so với cần thiết): Feasibility check pass ngay cả với k = 1, vậy binary search tìm được 1. Không vấn đề gì.

Overflow trong can_finish: Mỗi đống đóng góp tối đa pile / 1 = pile giờ, và pile <= 10^9. Với tối đa 10^4 đống, tổng có thể đạt 10^13, overflow một integer 32-bit. Trong Python điều này không bao giờ là vấn đề. Trong C#, biến total phải là long (64-bit), không phải int. Code ở trên đã dùng long total.

Các đống bằng nhau: Không cần xử lý đặc biệt. Công thức ceiling áp dụng đồng đều bất kể có giá trị lặp lại hay không.

Brute force so với binary search

Cả hai approach chia sẻ cùng inner loop can_finish — phần đó là O(n). Sự khác biệt hoàn toàn ở chỗ loop đó chạy bao nhiêu lần: tối đa max(piles) lần trong brute force so với nhiều nhất log2(10^9) ~= 30 lần trong binary search.

Brute force không hoàn toàn vô dụng — nó là statement rõ ràng nhất của "tôi muốn k nhỏ nhất mà predicate là true," đúng là specification mà binary search implement hiệu quả hơn. Viết brute force trước, rồi hỏi "tôi có thể binary search biến loop không?", là con đường khám phá hợp lệ.

Tôi sẽ ship phiên bản binary search. Brute force sẽ TLE với constraints đã cho, và code binary search không khó đọc hơn đáng kể — đặc biệt khi can_finish được tách ra thành helper có tên riêng.

Pattern cơ bản: binary search on the answer

Insight có thể chuyển giao là binary search không đòi hỏi mảng đã được sắp xếp. Nó chỉ cần một monotonic predicate trên một không gian có thứ tự tuyến tính. Bất cứ khi nào bạn có thể đóng khung một bài toán tối ưu hóa là "tìm giá trị tối thiểu x sao cho f(x) là true," và f monotonically non-decreasing, binary search áp dụng cho domain của x.

Cấu trúc luôn giống nhau:

1. Xác định search space (ở đây: [1, max(piles)]).
2. Viết feasibility check can_finish(k) chạy trong O(n) hoặc tốt hơn.
3. Binary search cho k trái nhất mà can_finish(k) là true.

Bài toán khoác câu chuyện về một con khỉ và chuối lên. Bóc lớp đó ra thì đây chỉ là "tìm điểm feasible tối thiểu."

Vị trí trong series binary search và những gì tiếp theo

Đây là bài thứ năm trong series. Những bài trước — classic binary search (704), find minimum in rotated sorted array (153), search in rotated sorted array (33), và search a 2D matrix (74) — đều binary search trong index space của một mảng có cấu trúc. Koko là bài đầu tiên trong series mà search space là một dải giá trị chúng ta tự xây dựng, không phải index của mảng.

Đó là bước khái niệm mà bài này thêm vào: binary search là công cụ cho bất kỳ tìm kiếm monotonic nào, không chỉ tra cứu vị trí trong mảng.

Capacity to Ship Packages Within D Days (LeetCode 1011) là sibling trực tiếp nhất. Thay "tốc độ ăn" bằng "capacity tàu chở hàng," piles bằng package weights, và hours bằng days. Feasibility check gần như giống hệt — tính tổng số chuyến cần ở capacity c và xem có vừa trong D ngày không. Shape hoàn toàn giống nhau; chỉ thay tên domain.

Split Array Largest Sum (LeetCode 410) lấy cùng pattern và hỏi minimum có thể của giá trị subarray sum lớn nhất khi bạn chia mảng thành m phần. Feasibility check hỏi "tôi có thể chia mảng này thành m phần mà mỗi phần tổng tối đa mid không?" — một greedy scan O(n) khác.

Minimum Number of Days to Make m Bouquets (LeetCode 1482) thêm spatial constraint: hoa phải liền kề nhau để tạo thành bó. Binary search trên ngày, rồi greedy đếm số bó có thể tạo đến ngày mid. Feasibility check vẫn là O(n).

Find the Smallest Divisor Given a Threshold (LeetCode 1283) gần như giống hệt cấu trúc với Koko: binary search một divisor d, và feasibility check tổng ceil(nums[i] / d) trên mảng. Nếu tổng đó nhỏ hơn hoặc bằng threshold, d được. Cùng cách tính ceiling division.

Twist trong mỗi sibling chỉ là một feasibility check khác — nhưng skeleton của binary search không thay đổi. Khi bạn đã thấy shape này trong Koko, bốn bài kia sẽ giải nhanh.