097 — Ship Packages Within D Days¶
096-এ Koko-র speed খুঁজলে। এই problem-টা পড়ে তোমার মনে হবে — "আরে, এটা তো একই জিনিস!" আর সেটাই আসল শিক্ষা: এক template, ভিন্ন গল্প। কলার speed-এর জায়গায় জাহাজের capacity, ঘণ্টার জায়গায় দিন। minimize BSoA-র চেহারা একবার চিনে ফেললে, নতুন প্রতিটা problem আসলে পুরনো বন্ধু নতুন পোশাকে। তবে এখানে check-এ একটা নতুন মোচড় আছে — packages ভাঙা যায় না, ক্রমও বদলানো যায় না।
Source¶
- Original source: LeetCode Capacity to Ship Packages Within D Days
- Platform: LeetCode — https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
- Topic: Math-based programming fundamentals → Level 7: Binary Search on Answer
- Difficulty: Medium
- Pattern: BSoA minimize (সবচেয়ে ছোট feasible capacity)
- Basic idea inherited from: 096 — Minimum Eating Speed
1. Problem in simple words¶
একটা conveyor belt-এ কতগুলো package সারিবদ্ধ, weights[i] হলো i-তম package-এর ওজন। তোমাকে এগুলো days দিনের মধ্যে জাহাজে পাঠাতে হবে।
নিয়ম: প্রতিদিন তুমি belt-এর সামনে থেকে ক্রম অনুযায়ী যত package নিতে চাও নাও, কিন্তু একদিনের মোট ওজন জাহাজের capacity ছাড়াতে পারবে না। ক্রম বদলানো যাবে না, একটা package ভাঙা যাবে না। প্রশ্ন: জাহাজের সবচেয়ে ছোট capacity কত, যাতে ঠিক days দিনে (বা কম) সব পাঠানো যায়?
2. What is the math idea?¶
আবার minimize ঘরানার BSoA — হুবহু 096-এর কাঠামো। উত্তর (capacity) সরাসরি বের না করে check লিখি: "এই capacity-তে কয় দিন লাগে, সেটা কি days-এর মধ্যে?"
observation — capacity বাড়লে দিন কমে (বা সমান)। তাই check-এর সিঁড়ি F F F T T T: ছোট capacity-তে বেশি দিন লাগে (পারে না), একটা জায়গার পর কুলিয়ে যায়। প্রথম T = সবচেয়ে ছোট feasible capacity।
3. Which basic idea does this inherit from?¶
096 (Minimum Eating Speed) থেকে — কাঠামো এক, শুধু গল্প আর check বদলেছে:
- Koko: answer = speed, check =
Σ ceil(pile/k) <= h - এখানে: answer = capacity, check =
প্রয়োজনীয় দিন <= days
কিন্তু একটা গুরুত্বপূর্ণ পার্থক্য check-এর ভেতরে: Koko-তে প্রতি স্তূপ আলাদা, তাই সরাসরি যোগ। এখানে packages ক্রমে সাজানো ও অবিভাজ্য — তাই দিন গুনতে greedy লাগে (যোগ করতে করতে capacity ছাড়ালেই নতুন দিন)। এই "check নিজেই একটা greedy পাস" — এটাই 099, 100-এর সাথে এর গভীর মিল।
4. Real-life analogy¶
ভাবো তুমি প্রতিদিন একটা ব্যাগে করে বাজার থেকে জিনিস আনো, কিন্তু জিনিসগুলো একটা লাইনে সাজানো আর তুমি লাইন ভেঙে নিতে পারো না — সামনে থেকে যা পড়ে তাই।
ব্যাগ ছোট হলে অল্প জিনিসে ভরে যায়, অনেক দিন লাগে সব আনতে। ব্যাগ বড় হলে কম দিনে হয়ে যায়। তুমি খুঁজছ সবচেয়ে ছোট ব্যাগ যা দিয়ে এখনো নির্দিষ্ট কয় দিনে সব আনা যায়। ব্যাগের size = capacity, যত দিন = days।
5. Visual explanation¶
weights = [1,2,3,4,5,6,7,8,9,10], days = 5। কয়েকটা capacity-র জন্য দিন আর "≤ 5?":
capacity : 14 15 16 17 ...
days_need: 6 5 5 5 ... (greedy-তে দিন গুনে)
≤ 5? : F T T T ...
↑
প্রথম T → উত্তর capacity = 15
cap=15-এ দিন ভাগ: [1,2,3,4,5]=15 | [6,7]=13 | [8]=8 (9 নিলে 17>15) | [9]=9 | [10]=10 → 5 দিন ✓
cap=14-এ: [1,2,3,4]=10 (5 নিলে 15>14) | [5,6]=11 | [7]=7 | [8]=8 | [9]=9 | [10] → 6 দিন ✗
সিঁড়ি F F F T T T — capacity বাড়লে দিন কমে, প্রথম T = সবচেয়ে ছোট feasible।
6. Example input and output¶
weights days -> min capacity (ব্যাখ্যা)
----------------------------------------------------------------
[1,2,3,4,5,6,7,8,9,10] 5 -> 15
[3,2,2,4,1,4] 3 -> 6
[1,2,3,1,1] 4 -> 3
[10,20,30] 1 -> 60 (1 দিন → সব একসাথে → sum)
[10,20,30] 3 -> 30 (3 দিন → প্রতি package আলাদা → max)
দুটো সীমান্ত edge: days = 1 হলে এক দিনেই সব → capacity = sum(weights)। days = package সংখ্যা হলে প্রতি package আলাদা দিনে → capacity = max(weights)। এই দুটোই answer space-এর দুই প্রান্ত।
7. Brute force thinking¶
capacity = max(weights) থেকে শুরু (এর কম হলে সবচেয়ে ভারী package-ই ওঠে না) করে এক এক করে বাড়াও, প্রথম যে capacity-তে দিন কুলোয় সেটাই উত্তর:
def ship_brute(weights, days):
def need(cap):
d, cur = 1, 0
for w in weights:
if cur + w > cap: # আজ আর ধরছে না → নতুন দিন
d += 1
cur = 0
cur += w
return d
cap = max(weights)
while need(cap) > days:
cap += 1
return cap
need(cap) greedy-তে দিন গোনে: যোগ করতে থাকো, capacity ছাড়ালে নতুন দিন শুরু। তারপর max(weights) থেকে capacity এক এক করে বাড়িয়ে প্রথম feasible-এ থামি।
8. Why brute force may be slow¶
capacity max(weights) থেকে sum(weights) পর্যন্ত যেতে পারে — সেই পরিসর বিশাল (10^9 স্কেল)। প্রতিটা capacity-তে need গুনতে O(n)। তাই O(n · sum(weights)) — অচল।
sum(weights) ≈ 5×10^9, n = 5×10^4 হলে:
brute force : ~10^14 operation (অসম্ভব ধীর, TLE)
binary search : ~33 × 5×10^4 ≈ 1.7×10^6 (O(n log sum), দ্রুত)
মূল শিক্ষা: need(cap) monotonic — তাই capacity এক এক করে না বাড়িয়ে binary search-এ অর্ধেক বাদ।
9. Better thinking¶
মূল insight: need(cap) monotonic decreasing, তাই need(cap) <= days-এর সিঁড়ি F F F T T T। প্রথম T খুঁজি:
def ship_within_days(weights, days):
def can(cap): # cap-এ days দিনে পারা যায়?
d, cur = 1, 0
for w in weights:
if cur + w > cap:
d += 1
cur = 0
cur += w
return d <= days
lo, hi = max(weights), sum(weights) # lo: সবচেয়ে ভারী তো উঠতেই হবে; hi: এক দিনে সব
while lo < hi:
mid = (lo + hi) // 2
if can(mid):
hi = mid # পারা যায় → আরও ছোট চেষ্টা
else:
lo = mid + 1 # পারা যায় না → বড় লাগবে
return lo
প্রতি ধাপে অর্ধেক, প্রতি check O(n) → O(n log(sum(weights)))।
10. Thinking tweak¶
আসল মোচড় দুটো। প্রথমত (096-এর মতোই): capacity সরাসরি না খুঁজে, প্রতিটা guess-কে check-এ পরিণত করো — can(cap) = 'এই capacity-তে days দিনে কুলোয়?'।
দ্বিতীয়ত, নতুন: answer space-এর সীমা সাবধানে। lo = max(weights) (এর কম হলে সবচেয়ে ভারী package কোনো দিনেই ওঠে না — কখনো feasible না), hi = sum(weights) (এক দিনে সব — সবসময় feasible)। 096-এ lo=1, hi=max; এখানে lo=max, hi=sum — সীমা problem-এর গল্প থেকে আসে, মুখস্থ না। সিঁড়ির দুই প্রান্তে কোনটা নিশ্চিত F আর কোনটা নিশ্চিত T — সেটা ভেবে নাও।
11. Step-by-step dry run¶
weights = [1,2,3,4,5,6,7,8,9,10], days = 5 (lo=max=10, hi=sum=55):
| step | lo | hi | mid | need(mid) | ≤ 5? | সিদ্ধান্ত |
|---|---|---|---|---|---|---|
| 1 | 10 | 55 | 32 | 2 | হ্যাঁ | hi = mid = 32 |
| 2 | 10 | 32 | 21 | 3 | হ্যাঁ | hi = mid = 21 |
| 3 | 10 | 21 | 15 | 5 | হ্যাঁ | hi = mid = 15 |
| 4 | 10 | 15 | 12 | 6 | না | lo = mid + 1 = 13 |
| 5 | 13 | 15 | 14 | 6 | না | lo = mid + 1 = 15 |
| — | 15 | 15 | — | — | — | lo == hi = 15 → return 15 |
উত্তর 15 ✓। step 3-এ need = 5 ≤ 5 (T), কিন্তু থামি না — আরও ছোট চেষ্টা; 12 আর 14-এ fail করে শেষে 15-এ স্থির। সেটাই সবচেয়ে ছোট feasible capacity।
12. Python solution¶
def ship_within_days(weights, days):
"""সবচেয়ে ছোট capacity যাতে weights ক্রমে days দিনে পাঠানো যায়।"""
def can(cap): # feasibility: days দিনে কুলোয়?
d, cur = 1, 0 # অন্তত 1 দিন লাগবেই
for w in weights:
if cur + w > cap: # আজ আর ধরছে না → নতুন দিন
d += 1
cur = 0
cur += w
return d <= days
lo, hi = max(weights), sum(weights) # lo নিশ্চিত নিচ, hi নিশ্চিত feasible
while lo < hi:
mid = (lo + hi) // 2
if can(mid):
hi = mid # পারা যায় → আরও ছোট
else:
lo = mid + 1 # পারা যায় না → বড় লাগবে
return lo
def ship_brute(weights, days): # ছোট input-এ cross-check
def need(cap):
d, cur = 1, 0
for w in weights:
if cur + w > cap:
d += 1
cur = 0
cur += w
return d
cap = max(weights)
while need(cap) > days:
cap += 1
return cap
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert ship_within_days([1,2,3,4,5,6,7,8,9,10], 5) == 15
assert ship_within_days([3,2,2,4,1,4], 3) == 6
assert ship_within_days([1,2,3,1,1], 4) == 3
assert ship_within_days([10,20,30], 1) == 60 # 1 দিন → sum
assert ship_within_days([10,20,30], 3) == 30 # n দিন → max
assert ship_within_days([5], 1) == 5 # এক package
# brute force-এর সাথে random cross-check
import random
random.seed(11)
for _ in range(300):
n = random.randint(1, 7)
w = [random.randint(1, 15) for _ in range(n)]
days = random.randint(1, n) # 1 ≤ days ≤ n যাতে feasible
assert ship_within_days(w, days) == ship_brute(w, days)
# boundary: উত্তর cap পারে, cap-1 পারে না
w, days = [1,2,3,4,5,6,7,8,9,10], 5
cap = ship_within_days(w, days)
def need(weights, c):
d, cur = 1, 0
for x in weights:
if cur + x > c:
d += 1; cur = 0
cur += x
return d
assert need(w, cap) <= days
assert need(w, cap - 1) > days
print(ship_within_days([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(ship_within_days([10,20,30], 1)) # 60
print("সব test pass!")
13. Line-by-line explanation¶
d = দিন গণনা (অন্তত 1 দিন তো লাগবেই), cur = আজকের দিনে এ পর্যন্ত তোলা মোট ওজন।
আজকের ওজনে এই package যোগ করলে capacity ছাড়িয়ে যায় → এই package আজ নয়, নতুন দিন শুরু (d += 1), আজকের বোঝা শূন্য থেকে শুরু।
package-টা চলতি দিনে যোগ করি। (লক্ষ করো: cur > cap কখনো হবে না কারণ lo >= max(weights), তাই একটা package একা সবসময় ধরে।)
answer space। lo = max(weights): সবচেয়ে ভারী package তো এক দিনে উঠতেই হবে, তার চেয়ে ছোট capacity কখনো কাজ করবে না। hi = sum(weights): এক দিনেই সব — সবসময় feasible, নিরাপদ উপরের সীমা।
minimize move: পারলে ছোট খুঁজি (hi = mid), না পারলে বড় লাগবে (lo = mid + 1)। 096-এর সাথে হুবহু এক।
cross-check-এ random brute force আর boundary (cap পারে, cap-1 পারে না)। সব মিললে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম: ship_within_days([1..10], 5) = 15 (dry run-এর ফল)। দ্বিতীয়: [10,20,30] days=1-এ = 60 (এক দিন → sum)। আগের সব assert — random cross-check (300 কেস) আর boundary যাচাই — চুপচাপ pass। সবশেষে সব test pass!।
15. Time complexity¶
O(n log(sum(weights))) — answer space [max, sum]-এ binary search (log(sum) ধাপ), প্রতি ধাপে check-এ সব n package-এ greedy পাস (O(n))। বড় input-এও দ্রুত।
16. Space complexity¶
O(1) — check-এ শুধু d, cur দুটো counter; কোনো বাড়তি array না। lo, hi, mid ছাড়া আর কিছু লাগে না।
17. Common mistakes¶
lo = 1বাlo = 0দিয়ে শুরু — capacity যদিmax(weights)-এর ছোট হয়, সবচেয়ে ভারী package কোনো দিনেই ওঠে না;lo = max(weights)।d0 থেকে শুরু করা — অন্তত 1 দিন লাগবেই;d = 1দিয়ে শুরু, নইলে দিন এক কম গোনা হয়।- package ভাঙা/ক্রম বদলানো ধরে নেওয়া — এই problem-এ ক্রম স্থির ও package অবিভাজ্য; greedy-তে সামনে থেকেই নিতে হয়।
- minimize move উল্টে ফেলা — পারলে
hi = mid, না পারলেlo = mid+1। (maximize-এর সাথে গুলিও না।) cur + w > cap-এর জায়গায়>=লেখা —>=দিলে ঠিক capacity-পূর্ণ দিনও ভেঙে যায়, দিন বেশি গোনা হয়।>সঠিক।
18. Harder problems that inherit this idea¶
- LeetCode — Split Array Largest Sum (https://leetcode.com/problems/split-array-largest-sum/) — হুবহু একই greedy check, শুধু গল্প "K ভাগে ভাঙা"; problem 100-এ বিস্তারিত।
- LeetCode — Divide Chocolate (https://leetcode.com/problems/divide-chocolate/) — উল্টো দিক (maximize the minimum), কিন্তু একই greedy-পাস চিন্তা।
- 099 (Allocate Minimum Pages) আর 100 (Split Array Largest Sum) — এই repo-রই পরের ধাপ; "minimize the maximum load" পরিবারের সরাসরি আত্মীয়।
19. Pattern learned¶
BSoA minimize with greedy feasibility — answer = capacity, check = greedy পাসে দিন গুনে <= days; lo = max, hi = sum; পাশ → hi = mid। বড় শিক্ষা: check নিজেই একটা ছোট greedy হতে পারে (যোগ করো, সীমা ছাড়ালে নতুন bucket) — আর answer space-এর সীমা problem-এর গল্প থেকেই আসে, মুখস্থ না। Koko-র সাথে এর হাড়-পাঁজর এক।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "Ship Packages = minimize BSoA, Koko-র যমজ; answer = capacity, check = greedy-তে দিন গুনে ≤ days, lo=max(w), hi=sum(w), পাশ→hi=mid। ক্রম স্থির + package অবিভাজ্য বলে check-এ greedy লাগে। 'minimize the max load' শুনলেই এই ছক।"
পরের ধাপ → 098 — Aggressive Cows (এবার maximize! সিঁড়ি উল্টে TTTFFF, move-ও উল্টো)। সম্পর্কিত → 096 — Minimum Eating Speed।
ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।