Optimal Cargo Allocation — Problem Statement & Solution Guide
Problem Description
You are managing a logistics operation where a single transport vehicle has a strict weight limit. You are provided with an array of individual cargo unit weights and the maximum load capacity of the vehicle. Your objective is to determine the maximum count of cargo units that can be loaded onto the vehicle without exceeding its weight limit. To maximize the number of units, you must prioritize lighter cargo. The solution requires selecting a subset of the available units such that their sum is less than or equal to the capacity, while the size of this subset is as large as possible.
Input: An integer array weights representing the mass of each available cargo unit, and an integer capacity representing the maximum weight the vehicle can carry.
Output: Return an integer representing the maximum number of cargo units that can be allocated. If no unit fits, return 0.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Optimal Cargo Allocation"
WHY DOES IT MATTER?
The sorting‑then‑greedy pattern is fundamental for problems where items have uniform benefit and differing costs; it transforms a combinatorial explosion into a linear scan after ordering, enabling scalable solutions.
OPTIMIZATION CHALLENGE
The key insight is the exchange argument that proves any optimal solution can be reordered to match the greedy order, allowing us to discard exponential subset checks.
REAL-WORLD CONNECTION
Think of loading a delivery truck: you first load the smallest packages to fit as many as possible, similar to how cloud schedulers pack lightweight tasks onto limited‑capacity nodes before larger ones.
In an interview, sort the array first, then use a simple loop with a running sum; remember to break as soon as adding the next weight exceeds capacity to avoid unnecessary iterations.
COMPLEXITY AT A GLANCE
O(n log n)O(1) additional (or O(n) if the sort is not in‑place)Core Theory — Why This Approach?
The problem can be modeled as a variant of the classic knapsack where the objective is to maximize the count of items rather than total value. A greedy strategy works because each item contributes equally to the objective (one unit) and only differs in weight; therefore, selecting lighter items first always leaves the most remaining capacity for additional items. Naïve enumeration of all subsets (2^n) quickly becomes infeasible for n > 30, as the exponential blow‑up exceeds typical time limits. By sorting the cargo weights in non‑decreasing order and iteratively adding them until the capacity would be breached, we achieve an optimal solution in O(n log n) time, which is optimal for comparison‑based sorting.
The underlying algorithmic paradigm is a "sorting‑then‑greedy" pattern, common in resource‑allocation problems where the utility of each element is uniform. This approach leverages the exchange argument: if an optimal solution contains a heavier item while a lighter unused item exists, swapping them cannot decrease the total count and may free capacity for more items. Hence, any optimal solution can be transformed into the greedy one, proving its optimality.
Interview Questions on This Problem
Q1How would you modify the solution if each cargo unit also had a profit value and you needed to maximize total profit while staying within the weight limit?
The problem becomes the classic 0/1 knapsack, requiring dynamic programming O(n·W) time or a meet‑in‑the‑middle approach for large capacities. Greedy by weight no longer guarantees optimal profit.
Q2Can you solve the problem in O(n) time without sorting? Under what constraints is this possible?
If the weight range is bounded (e.g., weights ≤ 10^5), counting sort or bucket sort can achieve linear time. Otherwise, sorting is necessary for the general case.
Q3Explain how you would handle the case where the vehicle can make multiple trips, each with the same capacity, and you want to minimize the number of trips needed to transport all cargo.
Sort the weights descending and apply a two‑pointer bin‑packing (first‑fit‑decreasing) heuristic; while not optimal for all instances, it yields a good approximation and runs in O(n log n).
Examples
Input
weights = [10, 5, 8, 2, 7], capacity = 15
Output
3
Explanation: Sort the weights in ascending order: [2, 5, 7, 8, 10]. Accumulate weights starting from the lightest: 2 (count=1, sum=2), 5 (count=2, sum=7), 7 (count=3, sum=14). The next weight is 8, which would make the sum 22, exceeding the capacity of 15. Thus, the maximum number of units is 3.
Input
weights = [100, 200, 300], capacity = 50
Output
0
Explanation: Sort the weights: [100, 200, 300]. The lightest unit weighs 100, which exceeds the capacity of 50. Therefore, no units can be loaded, and the result is 0.
Input
weights = [1, 1, 1, 1, 1], capacity = 3
Output
3
Explanation: Sort the weights: [1, 1, 1, 1, 1]. Accumulate: 1 (count=1, sum=1), 1 (count=2, sum=2), 1 (count=3, sum=3). The next 1 would make the sum 4, exceeding the capacity of 3. The maximum count is 3.
Input
weights = [5, 10, 15, 20], capacity = 35
Output
3
Explanation: Sort the weights: [5, 10, 15, 20]. Accumulate: 5 (count=1, sum=5), 10 (count=2, sum=15), 15 (count=3, sum=30). The next weight is 20, which would make the sum 50, exceeding the capacity of 35. The maximum count is 3.
Constraints
- 1 <= weights.length <= 10^5
- 1 <= weights[i] <= 10^9
- 1 <= capacity <= 10^14
Optimal Approach & Strategy
Sort the weights ascending and greedily pick items from the smallest until the capacity would be exceeded.
Brute Force Approach
Enumerate every subset of cargo, compute its total weight, and track the largest subset size that stays within the limit.
Verified Code Solutions
function solution(weights, capacity) {
weights.sort((a, b) => b - a);
let totalWeight = 0;
let cratesAllocated = 0;
for (let weight of weights) {
if (totalWeight + weight <= capacity) {
totalWeight += weight;
cratesAllocated++;
} else {
break;
}
}
return cratesAllocated;
}class Solution {
public:
int solution(vector<int>& weights, int capacity) {
sort(weights.rbegin(), weights.rend());
int totalWeight = 0;
int cratesAllocated = 0;
for (int weight : weights) {
if (totalWeight + weight <= capacity) {
totalWeight += weight;
cratesAllocated++;
} else {
break;
}
}
return cratesAllocated;
}
};class Solution {
public int solution(int[] weights, int capacity) {
Arrays.sort(weights);
int totalWeight = 0;
int cratesAllocated = 0;
for (int weight : weights) {
if (totalWeight + weight <= capacity) {
totalWeight += weight;
cratesAllocated++;
} else {
break;
}
}
return cratesAllocated;
}
}def solution(weights, capacity):
weights.sort(reverse=True)
total_weight = 0
crates_allocated = 0
for weight in weights:
if total_weight + weight <= capacity:
total_weight += weight
crates_allocated += 1
else:
break
return crates_allocatedfunction solution(weights, capacity) {
weights.sort((a, b) => b - a);
let totalWeight = 0;
let cratesAllocated = 0;
for (let weight of weights) {
if (totalWeight + weight <= capacity) {
totalWeight += weight;
cratesAllocated++;
} else {
break;
}
}
return cratesAllocated;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.