Đề bài: Mảng weights (trọng lượng gói hàng), D ngày. Mỗi ngày load tuần tự từ đầu mảng, tổng weight ≤ capacity. Tìm capacity nhỏ nhất để ship xong trong D ngày.
Ví dụ: weights=[3,2,2,4,1,4], D=3 → capacity=6 (ngày1: 3+2, ngày2: 2+4, ngày3: 1+4).
Ý tưởng: Binary Search Capacity + Greedy Check
- Capacity min =
max(weights)(phải chứa được gói heaviest). - Capacity max =
sum(weights)(ship tất cả 1 ngày). - Binary search trên [min, max]: check(mid) = có ship xong trong D ngày không?
- Check: greedy load tuần tự, đếm ngày cần.
Code Python
class Solution:
def shipWithinDays(self, weights: list[int], days: int) -> int:
def can_ship(capacity):
d = 1
curr = 0
for w in weights:
if curr + w > capacity:
d += 1
curr = 0
curr += w
return d <= days
left, right = max(weights), sum(weights)
while left < right:
mid = (left + right) // 2
if can_ship(mid):
right = mid
else:
left = mid + 1
return left
# Test
ob = Solution()
print(ob.shipWithinDays([3,2,2,4,1,4], 3)) # 6
print(ob.shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(ob.shipWithinDays([1,2,3,1,1], 4)) # 3
Phân tích
- Time:
O(n log(sum))- n = len(weights), sum = total weight. - Space:
O(1). - Check function O(n), binary search O(log(sum)).
Tại sao Binary Search đúng?
Monotonicity: nếu capacity = C có thể ship → mọi capacity > C cũng ship được. Hàm check đơn điệu.
Kết luận
Pattern "Binary Search on Answer" + "Greedy Check" rất phổ biến: minimize maximum / maximize minimum. Capacity, time, speed, etc.