Minimize Truck Trips — Problem Statement & Solution Guide
Problem Description
Given a set of crates with unique weights and a set of trucks with varying capacities, determine the optimal way to load the crates onto the trucks to minimize the number of trips required. The input will be a list of crate weights and a list of truck capacities. The output will be the minimum number of trips required to load all crates.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Minimize Truck Trips"
WHY DOES IT MATTER?
Efficient bin‑packing directly impacts logistics cost, resource utilization, and latency in distributed systems where tasks must be assigned to servers with limited capacity.
OPTIMIZATION CHALLENGE
The key insight is to sort both lists and then use a two‑pointer scan: pairing the heaviest remaining crate with the lightest that still fits eliminates wasted space without exhaustive search, collapsing an exponential problem to O(n log n).
REAL-WORLD CONNECTION
Think of a cloud scheduler assigning containers (crates) to VMs (trucks). Minimizing the number of VMs spun up reduces infrastructure spend, just as minimizing truck trips cuts fuel and labor costs.
During an interview, implement the greedy loop first with clear variable names (heavyIdx, lightIdx, truckIdx). If you get stuck, pause and write down a few small examples on paper; the pattern emerges quickly.
COMPLEXITY AT A GLANCE
O(n log n + m log m)O(n + m)Core Theory — Why This Approach?
The problem is a variant of the classic Bin Packing problem, where each truck represents a bin with a fixed capacity and each crate is an item with a unique weight. Bin Packing is NP‑hard, so a brute‑force enumeration of all possible assignments (trying every subset of crates for every truck) explodes exponentially as the number of crates grows. The optimal paradigm for interview‑scale inputs relies on a greedy, two‑pointer strategy combined with sorting: first sort crates in descending order and trucks in descending capacity. Then, for each truck, place the heaviest remaining crate that fits; if there is leftover capacity, pair it with the lightest crate that can still be accommodated. This “largest‑first, then smallest‑fit” approach is a practical implementation of the Best‑Fit Decreasing heuristic, which yields a solution within a constant factor of the optimum and runs in near‑linear time for typical constraints.
Interview Questions on This Problem
Q1How would you modify the greedy algorithm if each truck could make at most two trips instead of one?
Treat each truck as two identical bins of the same capacity. Duplicate the truck list, sort the expanded list, and run the same two‑pointer greedy assignment. This preserves the optimality of the Best‑Fit Decreasing heuristic while respecting the two‑trip limit.
Q2Explain why the simple “fit‑largest‑crate‑first” without pairing with the lightest crate can lead to sub‑optimal trip counts.
Placing only the largest crate may leave a large amount of unused capacity that could have been filled by a small crate. Subsequent trucks may then be forced to carry those small crates alone, increasing the total number of trips. Pairing the heaviest with the lightest maximizes bin utilization and reduces the overall count.
Q3In a system where truck capacities change dynamically (e.g., due to fuel load), how would you adapt your solution to handle real‑time updates?
Maintain the trucks in a balanced binary search tree keyed by remaining capacity. When a capacity changes, update its key in O(log m). For each incoming crate, perform a lower‑bound search to find the smallest truck that can accommodate it, achieving O(log m) per insertion while preserving near‑optimal packing.
Examples
Input
[1, 2, 3], [3, 4]
Output
2
Explanation: Step-by-step: with input [1, 2, 3] representing the weights of the crates and [3, 4] representing the capacities of the trucks, we first load crate 3 into the truck with capacity 4, then load crates 1 and 2 into the truck with capacity 3, resulting in 2 trips
Input
[5, 5, 5], [10, 10]
Output
2
Explanation: Step-by-step: with input [5, 5, 5] representing the weights of the crates and [10, 10] representing the capacities of the trucks, we first load two crates into one truck, then load the remaining crate into the other truck, resulting in 2 trips
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Sort crates and trucks, then greedily assign the heaviest crate to the largest available truck and fill remaining space with the lightest fitting crate using a two‑pointer scan.
Brute Force Approach
Enumerate every possible assignment of crates to trucks (or trips) and keep the configuration with the smallest number of trips; this requires exponential time.
Verified Code Solutions
function solution(crates, trucks) {
crates.sort((a, b) => b - a);
trucks.sort((a, b) => b - a);
let trips = 0;
let i = 0;
let j = 0;
while (i < crates.length) {
if (j >= trucks.length) {
trips++;
j = 0;
}
if (crates[i] <= trucks[j]) {
i++;
j++;
} else {
trips++;
j = 0;
}
}
return trips;
}class Solution {
public:
int solution(vector<int>& crates, vector<int>& trucks) {
sort(crates.rbegin(), crates.rend());
sort(trucks.rbegin(), trucks.rend());
int trips = 0;
int i = 0;
int j = 0;
while (i < crates.size()) {
if (j >= trucks.size()) {
trips++;
j = 0;
}
if (crates[i] <= trucks[j]) {
i++;
j++;
} else {
trips++;
j = 0;
}
}
return trips;
}
};class Solution {
public int solution(int[] crates, int[] trucks) {
Arrays.sort(crates);
Arrays.sort(trucks);
int trips = 0;
int i = crates.length - 1;
int j = trucks.length - 1;
while (i >= 0) {
if (j < 0) {
trips++;
j = trucks.length - 1;
}
if (crates[i] <= trucks[j]) {
i--;
j--;
} else {
trips++;
j = trucks.length - 1;
}
}
return trips;
}
}def solution(crates, trucks):
crates.sort(reverse=True)
trucks.sort(reverse=True)
trips = 0
i = 0
j = 0
while i < len(crates):
if j >= len(trucks):
trips += 1
j = 0
if crates[i] <= trucks[j]:
i += 1
j += 1
else:
trips += 1
j = 0
return tripsfunction solution(crates, trucks) {
crates.sort((a, b) => b - a);
trucks.sort((a, b) => b - a);
let trips = 0;
let i = 0;
let j = 0;
while (i < crates.length) {
if (j >= trucks.length) {
trips++;
j = 0;
}
if (crates[i] <= trucks[j]) {
i++;
j++;
} else {
trips++;
j = 0;
}
}
return trips;
}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.