Minimize Weighted Crate Loads — Problem Statement & Solution Guide
Problem Description
Given a list of integers crates representing the weights of the crates and a list of integers vehicles representing the maximum weight capacities of the transport vehicles, determine the maximum number of crates that can be loaded onto the vehicles without exceeding their weight capacities.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Minimize Weighted Crate Loads"
WHY DOES IT MATTER?
The greedy‑with‑sorted‑arrays pattern is a cornerstone for resource‑allocation problems where the objective is to maximize count under capacity constraints. Recognizing that ordering by size creates a matroid structure lets you prove optimality with simple exchange arguments, a skill that recurs in scheduling, load‑balancing, and memory allocation interviews.
OPTIMIZATION CHALLENGE
The key insight is that you never need to consider placing a heavier crate before a lighter one because doing so can only reduce the remaining capacity for future crates. By sorting once and using a data structure that can fetch the minimal feasible vehicle in logarithmic time, you collapse an exponential search space to linear‑ithmic time.
REAL-WORLD CONNECTION
Think of a warehouse loading dock where pallets (crates) are loaded onto trucks (vehicles). The dispatcher always loads the lightest pallet onto the smallest truck that can still carry it, ensuring the most pallets leave the dock each shift – a direct analogue to the algorithm.
In an interview, implement the two‑pointer version first (both arrays sorted). If the interviewer probes for better worst‑case guarantees, switch to a multiset/BST to achieve O(log m) look‑ups, and be ready to discuss why the greedy choice is provably optimal.
COMPLEXITY AT A GLANCE
O((n + m) log (n + m))O(m)Core Theory — Why This Approach?
The problem is a variant of the Multiple‑Knapsack (or Bin Packing) problem where the objective is to maximize the number of items placed rather than the total value. A naive exhaustive search would try every possible subset of crates for every vehicle, leading to exponential time (O(2^n) or worse) and quickly becomes infeasible for n, m > 30. The optimal paradigm leverages a greedy strategy backed by a matroid‑like exchange argument: sorting crates by weight (ascending) and always assigning each crate to the vehicle with the smallest remaining capacity that can still accommodate it. This works because placing a lighter crate in a tighter vehicle never harms the ability to place heavier crates later, guaranteeing a globally optimal count. The algorithm can be implemented with two sorted arrays and a pointer, or more generally with a balanced binary search tree (multiset) to retrieve the minimal feasible vehicle in O(log m) per crate, yielding O((n+m) log (n+m)) overall.
Interview Questions on This Problem
Q1How would you modify the solution if each vehicle could only carry a single crate?
If each vehicle can hold at most one crate, the problem reduces to a classic bipartite matching where we just need to count how many crates can be paired with a vehicle of sufficient capacity. Sorting both arrays and using a two‑pointer scan gives the answer in O(n log n + m log m) – increment both pointers when a match is found, otherwise advance the vehicle pointer.
Q2What changes are required if the goal shifts from maximizing the number of crates to maximizing the total weight loaded?
Maximizing total weight turns the problem into a classic Multiple‑Knapsack with values equal to weights, which is NP‑hard. A practical approach is to use a DP over total capacity (pseudo‑polynomial) for small capacities, or apply a greedy heuristic like sorting crates by weight descending and assigning each to the vehicle with the most remaining capacity, acknowledging it may not be optimal.
Q3Explain how you would handle the case where vehicle capacities can be updated dynamically (e.g., a vehicle becomes unavailable or its capacity changes) while still answering queries for the maximum crate count efficiently.
Maintain the vehicle capacities in a balanced BST or a Fenwick tree keyed by capacity. When a capacity changes, update the structure in O(log m). For each query, iterate through the sorted crates and for each perform a lower‑bound search in the BST to find the smallest feasible vehicle, removing it once assigned. This preserves the O((n+q) log m) amortized complexity where q is the number of dynamic updates.
Examples
Input
[5, 1, 3, 6, 7], [10, 15]
Output
4
Explanation: Step-by-step: with input [5, 1, 3, 6, 7] for crates and [10, 15] for vehicles, we first sort the crates in descending order to maximize the weight loaded onto each vehicle. Then, we iterate through the sorted crates and assign them to the vehicles based on their capacities. For the given input, the first vehicle can load 2 crates of weight 6 and 3, and the second vehicle can load 2 crates of weight 5 and 1, resulting in a total of 4 crates loaded.
Input
[1, 2, 3, 4, 5], [10, 10]
Output
5
Explanation: Step-by-step: with input [1, 2, 3, 4, 5] for crates and [10, 10] for vehicles, we can load all 5 crates onto the vehicles. The first vehicle can load crates of weight 1, 2, 3, and 4, and the second vehicle can load the crate of weight 5, resulting in a total of 5 crates loaded.
Constraints
- 1 <= crates length <= 1000
- 1 <= vehicles length <= 100
- 1 <= crate weight <= 1000
- 1 <= vehicle capacity <= 10000
Optimal Approach & Strategy
Sort both lists and greedily match each smallest crate to the smallest vehicle that can accommodate it, using a binary‑search tree for O(log m) look‑ups.
Brute Force Approach
Try every possible assignment of crates to vehicles, checking all subsets and permutations, which explodes exponentially with input size.
Verified Code Solutions
function solution(crates, vehicles) {
crates.sort((a, b) => b - a);
vehicles.sort((a, b) => b - a);
let count = 0;
for (let i = 0; i < vehicles.length; i++) {
let capacity = vehicles[i];
for (let j = 0; j < crates.length; j++) {
if (crates[j] <= capacity) {
count++;
capacity -= crates[j];
crates.splice(j, 1);
j--;
}
}
}
return count;
}class Solution {
public:
int solution(vector<int>& crates, vector<int>& vehicles) {
sort(crates.rbegin(), crates.rend());
sort(vehicles.rbegin(), vehicles.rend());
int count = 0;
for (int i = 0; i < vehicles.size(); i++) {
int capacity = vehicles[i];
for (int j = 0; j < crates.size(); j++) {
if (crates[j] <= capacity) {
count++;
capacity -= crates[j];
crates.erase(crates.begin() + j);
j--;
}
}
}
return count;
}
};import java.util.Arrays;
public class Solution {
public int solution(int[] crates, int[] vehicles) {
Arrays.sort(crates);
Arrays.sort(vehicles);
int count = 0;
int[] sortedCrates = new int[crates.length];
for (int i = crates.length - 1; i >= 0; i--) {
sortedCrates[crates.length - 1 - i] = crates[i];
}
for (int i = vehicles.length - 1; i >= 0; i--) {
int capacity = vehicles[i];
for (int j = 0; j < sortedCrates.length; j++) {
if (sortedCrates[j] <= capacity) {
count++;
capacity -= sortedCrates[j];
sortedCrates[j] = 0;
}
}
}
return count;
}
}def solution(crates, vehicles):
crates.sort(reverse=True)
vehicles.sort(reverse=True)
count = 0
for i in range(len(vehicles)):
capacity = vehicles[i]
j = 0
while j < len(crates):
if crates[j] <= capacity:
count += 1
capacity -= crates[j]
crates.pop(j)
else:
j += 1
return countfunction solution(crates, vehicles) {
crates.sort((a, b) => b - a);
vehicles.sort((a, b) => b - a);
let count = 0;
for (let i = 0; i < vehicles.length; i++) {
let capacity = vehicles[i];
for (let j = 0; j < crates.length; j++) {
if (crates[j] <= capacity) {
count++;
capacity -= crates[j];
crates.splice(j, 1);
j--;
}
}
}
return count;
}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.