097 — Ship Packages Within D Days¶
096-এ Koko-র speed খুঁজলে। এই problem-টা পড়ে তোমার মনে হবে — "আরে, এটা তো একই জিনিস!" আর সেটাই আসল শিক্ষা: এক template, ভিন্ন গল্প। কলার speed-এর জায়গায় জাহাজের capacity, ঘণ্টার জায়গায় দিন। minimize BSoA-র চেহারা একবার চিনে ফেললে, নতুন প্রতিটা problem আসলে পুরনো বন্ধু নতুন পোশাকে। তবে এখানে check-এ একটা নতুন মোচড় আছে — packages ভাঙা যায় না, ক্রমও বদলানো যায় না।
Problem link ও উৎস
- 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
প্রশ্ন ও উদাহরণ¶
সহজ করে প্রশ্ন¶
একটা conveyor belt-এ কতগুলো package সারিবদ্ধ, weights[i] হলো i-তম package-এর ওজন। তোমাকে এগুলো days দিনের মধ্যে জাহাজে পাঠাতে হবে।
নিয়ম: প্রতিদিন তুমি belt-এর সামনে থেকে ক্রম অনুযায়ী যত package নিতে চাও নাও, কিন্তু একদিনের মোট ওজন জাহাজের capacity ছাড়াতে পারবে না। ক্রম বদলানো যাবে না, একটা package ভাঙা যাবে না। প্রশ্ন: জাহাজের সবচেয়ে ছোট capacity কত, যাতে ঠিক days দিনে (বা কম) সব পাঠানো যায়?
Input ও 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-এর দুই প্রান্ত।
চেনা উদাহরণে বোঝা¶
ভাবো তুমি প্রতিদিন একটা ব্যাগে করে বাজার থেকে জিনিস আনো, কিন্তু জিনিসগুলো একটা লাইনে সাজানো আর তুমি লাইন ভেঙে নিতে পারো না — সামনে থেকে যা পড়ে তাই।
ব্যাগ ছোট হলে অল্প জিনিসে ভরে যায়, অনেক দিন লাগে সব আনতে। ব্যাগ বড় হলে কম দিনে হয়ে যায়। তুমি খুঁজছ সবচেয়ে ছোট ব্যাগ যা দিয়ে এখনো নির্দিষ্ট কয় দিনে সব আনা যায়। ব্যাগের size = capacity, যত দিন = days।
ভিত্তির ধারণা¶
আগের কোন ধারণাটি লাগবে¶
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-এর সাথে এর গভীর মিল।
ভেতরের অঙ্ক¶
আবার minimize ঘরানার BSoA — হুবহু 096-এর কাঠামো। উত্তর (capacity) সরাসরি বের না করে check লিখি: "এই capacity-তে কয় দিন লাগে, সেটা কি days-এর মধ্যে?"
observation — capacity বাড়লে দিন কমে (বা সমান)। তাই check-এর সিঁড়ি F F F T T T: ছোট capacity-তে বেশি দিন লাগে (পারে না), একটা জায়গার পর কুলিয়ে যায়। প্রথম T = সবচেয়ে ছোট feasible capacity।
ধাপে ধাপে সমাধান¶
প্রথম সরল উপায়¶
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-এ থামি।
কোথায় বেশি কাজ হতে পারে¶
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-এ অর্ধেক বাদ।
আরও ভালোভাবে ভাবা¶
মূল 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)))।
ভাবনার পরিবর্তন¶
আসল মোচড় দুটো। প্রথমত (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 — সেটা ভেবে নাও।
ছবিতে বোঝা¶
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।
ছোট input-এ ধাপে ধাপে¶
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।
কোড ও ব্যাখ্যা¶
Python¶
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!")
কোডের প্রতিটি অংশ¶
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!।
Output মিলিয়ে দেখা¶
চালালে যা ছাপবে:
প্রথম: 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!।
খরচ ও সাধারণ ভুল¶
সময়¶
O(n log(sum(weights))) — answer space [max, sum]-এ binary search (log(sum) ধাপ), প্রতি ধাপে check-এ সব n package-এ greedy পাস (O(n))। বড় input-এও দ্রুত।
অতিরিক্ত জায়গা¶
O(1) — check-এ শুধু d, cur দুটো counter; কোনো বাড়তি array না। lo, hi, mid ছাড়া আর কিছু লাগে না।
যে ভুলগুলো এড়াতে হবে¶
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-পূর্ণ দিনও ভেঙে যায়, দিন বেশি গোনা হয়।>সঠিক।
শেখা ও পরের অনুশীলন¶
এই ধারণার পরের অনুশীলন¶
- 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" পরিবারের সরাসরি আত্মীয়।
কৌশলটি মনে রাখুন¶
BSoA minimize with greedy feasibility — answer = capacity, check = greedy পাসে দিন গুনে <= days; lo = max, hi = sum; পাশ → hi = mid। বড় শিক্ষা: check নিজেই একটা ছোট greedy হতে পারে (যোগ করো, সীমা ছাড়ালে নতুন bucket) — আর answer space-এর সীমা problem-এর গল্প থেকেই আসে, মুখস্থ না। Koko-র সাথে এর হাড়-পাঁজর এক।
নিজেকে যাচাই করুন¶
ভবিষ্যতের আমাকে এক লাইনে: "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" লেখো।