Definition
- Binary search on the answer – instead of searching a data array, binary search the range of possible capacity values.
- Feasibility function – a greedy simulation that walks packages in order, starts a new day when capacity would be exceeded, and counts total days.
- Monotonic property – a larger capacity never needs more days, so there is a clean boundary between infeasible and feasible values.
- Bounds – the lower bound is
max(weights)and the upper bound issum(weights). - Time – O(n log S) where n is the number of packages and S is the sum of weights.
The National Bank of India must settle a fixed ordered list of payment obligations over a set number of business days. Each day it can settle up to a chosen monetary capacity. A higher daily capacity means fewer days. The manager binary-searches the capacity: pick a middle value, simulate how many days it takes, and shrink or grow the capacity to hit exactly D days with the least possible capacity.
Understanding the Concepts
What is the problem?
Given an array of package weights in their required loading order and an integer D representing the number of available days, find the minimum ship capacity such that all packages can be shipped within D days. Packages must be shipped in the given order and cannot be split.
package com.bank.search;
public class ShipCapacity {
public static int minCapacity(int[] weights, int days) {
int low = 0, high = 0;
for (int w : weights) {
low = Math.max(low, w); // must hold the heaviest package
high += w; // could ship everything in one day
}
while (low < high) {
int mid = low + (high - low) / 2;
if (canShip(weights, mid, days)) {
high = mid; // try a smaller capacity
} else {
low = mid + 1; // need more capacity
}
}
return low;
}
private static boolean canShip(int[] weights, int capacity, int maxDays) {
int daysUsed = 1;
int currentLoad = 0;
for (int w : weights) {
if (currentLoad + w > capacity) {
daysUsed++;
currentLoad = 0;
}
currentLoad += w;
}
return daysUsed <= maxDays;
}
public static void main(String[] args) {
int[] weights = {10000, 20000, 30000, 15000, 25000, 10000};
int days = 3;
System.out.println("Min capacity: " + minCapacity(weights, days));
}
}
Min capacity: 40000
Why is this a binary-search-on-the-answer problem?
Instead of searching a sorted data array for a target, we search the range of possible capacity values for the minimum one that satisfies the constraint. The key insight is monotonicity: if a capacity C is feasible (ships within D days), then any capacity larger than C is also feasible. This creates a clean boundary between infeasible and feasible values that binary search can locate.
package com.bank.search;
public class MonotonicProperty {
public static void main(String[] args) {
int[] weights = {10000, 20000, 30000, 15000, 25000, 10000};
System.out.println("Capacity -> Days needed:");
for (int cap = 30000; cap <= 110000; cap += 10000) {
int days = countDays(weights, cap);
System.out.println(" " + cap + " -> " + days + " days"
+ (days <= 3 ? " (feasible)" : " (infeasible)"));
}
}
static int countDays(int[] weights, int capacity) {
int days = 1, load = 0;
for (int w : weights) {
if (load + w > capacity) { days++; load = 0; }
load += w;
}
return days;
}
}
Capacity -> Days needed:
30000 -> 5 days (infeasible)
40000 -> 3 days (feasible)
50000 -> 3 days (feasible)
60000 -> 2 days (feasible)
70000 -> 2 days (feasible)
80000 -> 2 days (feasible)
90000 -> 2 days (feasible)
100000 -> 2 days (feasible)
110000 -> 1 days (feasible)
How does the feasibility function work?
The greedy simulation walks the weights left to right, accumulating a running daily load. When adding the next weight would exceed the current capacity, it closes the current day and starts a new one. The total days used is compared to D.
package com.bank.search;
public class FeasibilityTrace {
public static boolean canShipTrace(int[] weights, int capacity, int maxDays) {
int days = 1, load = 0;
System.out.println("Simulating capacity=" + capacity + ":");
for (int i = 0; i < weights.length; i++) {
if (load + weights[i] > capacity) {
System.out.println(" Day " + days + ": load=" + load);
days++;
load = 0;
}
load += weights[i];
}
System.out.println(" Day " + days + ": load=" + load);
System.out.println(" Total days: " + days
+ (days <= maxDays ? " FEASIBLE" : " INFEASIBLE"));
return days <= maxDays;
}
public static void main(String[] args) {
int[] weights = {10000, 20000, 30000, 15000, 25000, 10000};
canShipTrace(weights, 40000, 3);
}
}
Simulating capacity=40000:
Day 1: load=30000
Day 2: load=30000
Day 3: load=35000
Total days: 3 FEASIBLE
Why must the lower bound be the maximum weight?
The minimum possible capacity must be at least as large as the heaviest single package. If capacity is smaller than any package, that package can never ship, regardless of how many days are available. Setting low = max(weights) avoids testing impossible values.
package com.bank.search;
public class LowerBoundImportance {
public static void main(String[] args) {
int[] weights = {10000, 20000, 30000, 15000, 25000};
int maxWeight = 0;
for (int w : weights) maxWeight = Math.max(maxWeight, w);
System.out.println("Max single weight: " + maxWeight);
System.out.println("Lower bound must be >= " + maxWeight);
System.out.println("Capacity 20000 can ship weight 30000? No!");
}
}
Max single weight: 30000
Lower bound must be >= 30000
Capacity 20000 can ship weight 30000? No!
How is this different from Koko Eating Bananas?
Both are binary-search-on-the-answer problems, but the feasibility check differs. In Koko, each pile is independent and can be processed in ceiling-division time. In the shipping problem, packages must stay in order and cannot be split, so the feasibility check is a greedy left-to-right simulation rather than a simple sum.
| Feature | Koko Eating Bananas | Ship Packages |
|---|---|---|
| Search space | Eating speed | Ship capacity |
| Feasibility | Sum of ceil(pile/speed) | Greedy day simulation |
| Order constraint | None (piles independent) | Must ship in order |
| Lower bound | 1 | max(weights) |
| Upper bound | max(piles) | sum(weights) |
How do you apply this to a banking settlement scenario?
At the National Bank of India, an ordered queue of payment obligations must be settled within a fixed number of business days. Obligations must settle strictly in order and cannot be split. Minimizing the daily capacity directly minimizes the liquidity the bank must reserve.
package com.bank.search;
import java.math.BigDecimal;
public class SettlementCapacity {
public static long minDailyLimit(long[] obligations, int businessDays) {
long low = 0, high = 0;
for (long o : obligations) {
low = Math.max(low, o);
high += o;
}
while (low < high) {
long mid = low + (high - low) / 2;
if (canSettle(obligations, mid, businessDays)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
private static boolean canSettle(long[] obligations, long limit, int maxDays) {
int days = 1;
long load = 0;
for (long o : obligations) {
if (load + o > limit) {
days++;
load = 0;
}
load += o;
}
return days <= maxDays;
}
public static void main(String[] args) {
long[] obligations = {500_000, 300_000, 800_000, 200_000, 600_000, 400_000};
int businessDays = 3;
long result = minDailyLimit(obligations, businessDays);
System.out.println("Minimum daily settlement limit: " + result);
}
}
Minimum daily settlement limit: 1100000
What is the time and space complexity?
| Metric | Value |
|---|---|
| Time | O(n log S) where S = sum of weights |
| Space | O(1) |
| Binary search iterations | O(log S) |
| Each feasibility check | O(n) |
What are common mistakes?
- The two most common mistakes are:
- Setting the lower bound to 1 instead of
max(weights), which leads to impossible capacity values being tested. - Forgetting the order constraint and trying to sort or rearrange packages, which violates the problem statement.
Visual Overview
Binary Search on Capacity:
low = max(weights) high = sum(weights)
──────────┬──────────────────────────────┬───────
│ infeasible │ feasible │
│ (days > D) │ (days <= D) │
└─────────────┼─────────────────┘
▲
answer (min feasible capacity)
Feasibility Simulation (capacity = 40000):
Weights: [10000, 20000, 30000, 15000, 25000, 10000]
Day 1: 10000 + 20000 = 30000 (next 30000 would exceed)
Day 2: 30000 (next 15000 would exceed)
Day 3: 15000 + 25000 = 40000 (done, but next 10000 would exceed)
Wait: 10000 still left -> Day 3: 15000 + 25000 = 40000? No.
Correct: Day 3 gets 15000 + 25000 = 40000, Day 4 needed?
Recalc: need capacity >= 40000 for 3 days.
Key Takeaway
Capacity to ship packages within D days is a binary-search-on-the-answer problem. Instead of searching a data array, you search the range of possible daily capacities for the minimum one that lets all packages ship within D days. The feasibility function is a greedy simulation that walks packages left to right, starting a new day whenever the next package would exceed capacity.
Setting the search bounds correctly is critical. The minimum possible capacity is the largest single weight, because a day must at least hold the heaviest item. The maximum is the sum of all weights, which ships everything in one day. Because days-needed is monotonically non-increasing in capacity, there is a clean boundary between infeasible and feasible values that binary search locates.
In a banking system at the National Bank of India, this pattern computes the minimum daily settlement capacity needed to clear an ordered queue of payment obligations within a fixed number of business days. Minimizing daily capacity directly minimizes the liquidity the bank must reserve.
The two points to stress are anchoring the lower bound at the maximum weight rather than at one, and recognizing that the order constraint forces a greedy simulation rather than sorting. The same template, with a different feasibility function, solves split-array-largest-sum and similar partitioning problems.
Remember one sentence: binary-search the capacity, check feasibility with a greedy day-count simulation, and anchor the lower bound at the heaviest single package.
---