Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/koko-eating-bananas/description/
Table of Contents
1. Cách tiếp cận vấn đề
Bài toán cho 1 mảng gồm n cây chuối, mỗi cây chứa piles[i] trái chuối, Koko rất thích ăn chuối nhưng nó chỉ được ăn k trái chuối mỗi giờ trước khi người bảo vệ quay trở lại sau h giờ. Vì vậy mỗi giờ, Koko chọn cho mình 1 cột và ăn k trái chuối từ cột đó, nếu cột đó có ít hơn k trái chuối, nó sẽ ăn hết và sẽ tạm nghỉ ngơi cho đến hết giờ chứ không chuyển sang cột khác.
Yêu cầu của bài toán là trả về số k nhỏ nhất sao cho Koko có thể ăn hết chuối từ các cột trong khoảng h giờ (trước khi người bảo vệ quay trở về).
Bài toán cho ta các điều kiện
- 1 <= piles.length <= 10^4
- 1 <= piles[i] <= 10^9
- piles.length <= h <= 10^9
Example:
- Input: piles = [3,6,7,11], h = 8
- Output: 4
Explain
- Giờ đầu tiên: ăn hết 3 trái chuối từ piles[0] và nghỉ ngơi
- Giờ thứ hai: ăn 4 trái chuối từ piles[1], còn lại 6 - 4 = 2
- Giờ thứ ba: ăn hết 2 trái chuối còn lại từ piles[1] và nghỉ ngơi
- Giờ thứ tư: ăn 4 trái chuối từ piles[2], còn lại 7 - 4 = 3
- Giờ thứ năm: ăn hết 3 trái chuối còn lại từ piles[2] và nghỉ ngơi
- Giờ thứ sáu: ăn 4 trái chuối từ piles[3], còn lại 11 - 4 = 7
- Giờ thứ bảy: ăn 4 trái chuối từ piles[4], còn lại 7 - 4 = 3
- Giờ thứ tám: ăn hết 3 trái chuối còn lại từ piles[3] và kết thúc
- => Số giờ hoàn thành là 8 <= h = 8, nên k = 4 được tính là hợp lệ
Về idea chung, cơ bản chúng ta cần phải xác định được khoảng giá trị mà ta có thể giảm k, dễ thấy khoảng giá trị đó chính là [left, right] tương ứng [1, giá trị max trong mảng piles], trong ví dụ ở trên sẽ là [1, 11].
Sau khi xác định được khoảng giá trị rồi, vì đề bài bài yêu cầu là tìm k nhỏ nhất, nên ta sẽ giảm k trong khoảng giá trị đó, và với mỗi k:
- Ta sẽ đi qua từng cây chuối, và tính toán xem với mỗi cây thì sẽ cần bao nhiêu giờ để hoàn thành rồi tính tổng số giờ lại.
- Nếu tổng số giờ nhỏ hơn hoặc bằng h thì coi như k ok, có thể ghi nhận lại kết quả.
- Ngoài ra, có 1 điểm thú vị liên quan đến Toán học mà mình muốn giới thiệu ở bước tính số giờ này:
- Thay vì chúng ta tiếp cận bằng việc tính div và mod:
- Nếu (số lượng chuối % k == 0) thì số giờ hoàn thành tại cột đó = số lượng chuối / k.
- Ngược lại nếu số lượng chuối không chia hết cho k, thì số giờ hoàn thành tại cột đó = (số lượng chuối / k) + 1. Lý do + 1 là vì phần dư khi chia cho k sẽ nhỏ hơn k nên sẽ cần thêm 1 giờ nữa để hoàn thành
- Thì chúng ta sẽ áp dụng công thức sau, mục đích là để chuẩn hóa cho cả 2 trường hợp chia hết và không chia hết cho k:
- Số giờ hoàn thành tại mỗi cột = ((Số lượng chuối tại mỗi cột - 1) / k) + 1
Từ idea này, ta thấy bước duyệt qua từng cây chuối để tính số giờ hoàn thành sẽ là không đổi và không thể tối ưu được nữa, nên ta sẽ focus vòa bước giảm k và sẽ có 2 cách tiếp cận chính:
Cách 1: Áp dụng Linear Search, giảm k tuần tự từ biên phải - max value về biên trái - min value trong range. Với mỗi k ta sẽ tính toán tổng thời gian hoàn thành, và nếu <= h, ta sẽ ghi nhận và một biến tạm max. Time complexity sẽ là O(m*n)
Cách 2: Áp dụng Binary Search, cần phải xác định được khi nào tăng right hoặc giảm left, time complexity chung chắc chắn sẽ giảm xuống còn O(nlogm). Đây cũng là cách tối ưu nhất nên mình sẽ tập trung phân tích kỹ về nó.
n: số lượng phần tử trong mảng piles
m: max value trong mảng piles
2. Solution & Phân Tích
Có một tính chất quan trọng cần lưu ý đó chính là k sẽ nghịch biến với tổng số giờ hoàn thành.
- Nếu k tăng thì tổng số giờ hoàn thành sẽ giảm
- Nếu k giảm thì tổng số giờ hoàn thành sẽ tăng
Và bài toán yêu cầu tìm điểm giá trị mà tại đó k là nhỏ nhất còn tổng số giờ nhỏ hơn hoặc bằng h. Hay nói cách khác, ta cần tìm k nhỏ nhất sao cho tổng số giờ là lớn nhất tương ứng trên 2 khoảng giá trị của chúng:
- k: [1, giá trị max trong mảng piles]
- Tổng số giờ hoàn thành: [số lượng các phần tử trong mảng piles, h]
Đối với những bài toán tìm giá trị cực đại, ta sẽ có 1 template chung và trong trường hợp tìm cực tiểu thì biên phải right sẽ chính là nơi để store giá trị nhỏ nhất đó:
- Mỗi khi khoảng giá trị của k còn hợp lệ (left < right)
- Ta sẽ tính giá trị k = (left + right) / 2;
- Loop qua tất cả giá trị của mảng piles, tính tổng thời gian hoàn thành tương ứng với giá trị k, tạm gọi là totalTime.
- Nếu totalTime <= h (hợp lệ): gán right = k;
- Ngược lại nếu totalTime > h: gán left = k + 1;
Time-Complexity: O(nlog(m))
Space-Complexity: O(1) - In-place algorithm
n: số lượng phần tử trong mảng piles
m: max value trong mảng piles
3. Code
Để tối ưu hơn nữa, ta có thể tối ưu range value [left, right] bằng việc tính trung bình để tránh dư thừa, tuy nhiên để tránh phức tạp hóa mình sẽ không mention.
