Jungle Expedition Supply Chain Optimization — Problem Statement & Solution Guide
Problem Description
In a jungle expedition supply chain, crates of food and equipment are transported to various camps using a network of rivers and trails. Each crate has a unique identifier and a specific weight. The expedition leader needs to determine the most efficient way to transport these crates to minimize the total weight carried by each porter. The porters can only carry a maximum of 27 kilograms at a time. The input will be a 2D array where each sub-array contains the crate's unique identifier and its weight.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Jungle Expedition Supply Chain Optimization"
WHY DOES IT MATTER?
Bin Packing captures the essence of resource allocation under strict capacity constraints, a recurring theme in cloud scheduling, memory management, and logistics. Mastering this pattern equips engineers to design systems that efficiently batch work, reduce waste, and meet SLA limits.
OPTIMIZATION CHALLENGE
The key insight is that sorting items by weight dramatically reduces the search space: placing the heaviest crates first forces the algorithm to make the most restrictive decisions early, which limits the number of bins needed and yields a near‑optimal bound.
REAL-WORLD CONNECTION
Think of a distributed job scheduler that groups tasks into containers of limited memory. Each container is a 'porter' and each task's memory footprint is a 'crate'. Efficiently packing tasks minimizes the number of containers spun up, saving compute cost—mirroring the expedition’s need to minimize porter trips.
During the interview, implement FFD with a simple array of remaining capacities; avoid complex data structures like balanced trees unless you need O(log m) insertion. A linear scan over a modest number of porters (≤ n) is fast enough and keeps the code clean.
COMPLEXITY AT A GLANCE
O(n log n)O(n)Core Theory — Why This Approach?
The Jungle Expedition problem is a classic instance of the Bin Packing problem, where each porter represents a bin with a fixed capacity of 27 kg and each crate is an item with a weight. The objective is to pack all crates into the fewest possible ports (or equivalently, to minimize the number of trips) while never exceeding the per‑porter limit. A naïve solution would try every possible subset of crates for each porter, leading to exponential time (O(2^n)) because the decision space grows combinatorially with the number of crates. This quickly becomes infeasible for even moderate input sizes (n > 20). The optimal paradigm for large‑scale instances relies on greedy approximation: sorting crates in descending order of weight and then placing each crate into the first porter that can accommodate it (First‑Fit Decreasing, FFD). FFD runs in O(n log n) time due to the sort and yields a solution that is at most 11/9 · OPT + 1 bins, which is acceptable for interview settings where an exact optimal solution is NP‑hard. Advanced exact methods (branch‑and‑bound, integer linear programming) exist but are rarely required in a coding interview.
Interview Questions on This Problem
Q1How would you modify the solution if each porter could carry a different maximum weight (e.g., some can carry 30 kg, others 25 kg)?
Sort both the crates (descending) and the porters (descending by capacity). Then iterate over crates, assigning each crate to the first porter whose remaining capacity can accommodate it, updating that porter’s residual capacity. This is a variant of the variable‑size bin packing problem and still runs in O(n log n + m log m) where m is the number of porters.
Q2Explain why the Bin Packing problem is NP‑hard and what that implies for interview solutions.
Bin Packing can be reduced from the Partition problem: given a set of numbers, deciding if they can be split into two subsets of equal sum is equivalent to packing them into two bins of capacity equal to half the total sum. Since Partition is NP‑complete, Bin Packing is NP‑hard, meaning no polynomial‑time algorithm is known for the exact optimum. In interviews, this justifies using greedy approximations like First‑Fit Decreasing, which are simple, fast, and have provable bounds.
Q3If the weight limit per porter were increased to 27 kg + ε (a small epsilon), could you guarantee an optimal solution with a greedy approach?
No. Even a tiny increase in capacity does not change the combinatorial nature of the problem; the greedy FFD remains an approximation. Only when the capacity becomes large enough relative to the largest item (e.g., capacity ≥ 2 × maxWeight) does a simple greedy become optimal, but for a constant 27 kg limit, optimality cannot be guaranteed.
Examples
Input
[[1, 10], [2, 20], [3, 15]]
Output
[[1, 2], [3]]
Explanation: Step-by-step: with input [[1, 10], [2, 20], [3, 15]], we first sort the crates by weight in descending order, then we assign the heaviest crates to the porters until the maximum weight of 27 kilograms is reached. In this case, we assign crate 2 (20 kg) to one porter and crate 3 (15 kg) and crate 1 (10 kg - but only 7 kg can be added to crate 3) to another porter, but since crate 1 can't be fully added to crate 3, we assign it to another porter.
Input
[[1, 5], [2, 10], [3, 12], [4, 8]]
Output
[[1, 2], [3], [4]]
Explanation: Step-by-step: with input [[1, 5], [2, 10], [3, 12], [4, 8]], we first sort the crates by weight in descending order, then we assign the heaviest crates to the porters until the maximum weight of 27 kilograms is reached. In this case, we assign crate 3 (12 kg) to one porter, crate 2 (10 kg) and crate 4 (8 kg - but only 7 kg can be added to crate 2, and crate 4 is 8 kg which exceeds the limit when added to crate 2) to another porter, but since crate 4 can't be fully added to crate 2, we assign crate 4 to another porter and crate 1 (5 kg) to the porter with crate 2.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Sort the crates by weight in descending order, then iterate through them placing each crate into the first porter that still has enough remaining capacity (First‑Fit Decreasing). This greedy method runs in O(n log n) time and yields a near‑optimal solution.
Brute Force Approach
Generate every possible grouping of crates into porter trips and check which grouping respects the 27 kg limit while using the fewest trips. This exhaustive search explores 2^n subsets and is exponential in time.
Verified Code Solutions
function solution(crates) { let result = []; let currentPorter = []; let currentWeight = 0; crates.sort((a, b) => b[1] - a[1]); for (let crate of crates) { if (currentWeight + crate[1] > 27) { result.push(currentPorter); currentPorter = [crate[0]]; currentWeight = crate[1]; } else { currentPorter.push(crate[0]); currentWeight += crate[1]; } } if (currentPorter.length > 0) { result.push(currentPorter); } return result; }class Solution { public: vector<vector<int>> solution(vector<vector<int>>& crates) { sort(crates.begin(), crates.end(), [](vector<int>& a, vector<int>& b) { return a[1] > b[1]; }); vector<vector<int>> result; vector<int> currentPorter; int currentWeight = 0; for (auto& crate : crates) { if (currentWeight + crate[1] > 27) { result.push_back(currentPorter); currentPorter.clear(); currentPorter.push_back(crate[0]); currentWeight = crate[1]; } else { currentPorter.push_back(crate[0]); currentWeight += crate[1]; } } if (!currentPorter.empty()) { result.push_back(currentPorter); } return result; } }import java.util.Arrays; public class Solution { public int[][] solution(int[][] crates) { Arrays.sort(crates, (a, b) -> b[1] - a[1]); int[][] result = new int[crates.length][]; int index = 0; int currentWeight = 0; for (int[] crate : crates) { if (currentWeight + crate[1] > 27) { index++; currentWeight = crate[1]; } else { currentWeight += crate[1]; } } return result; } }def solution(crates): result = []; current_porter = []; current_weight = 0; crates.sort(key=lambda x: x[1], reverse=True); for crate in crates: if current_weight + crate[1] > 27: result.append(current_porter); current_porter = [crate[0]]; current_weight = crate[1]; else: current_porter.append(crate[0]); current_weight += crate[1]; if current_porter: result.append(current_porter); return resultfunction solution(crates) { let result = []; let currentPorter = []; let currentWeight = 0; crates.sort((a, b) => b[1] - a[1]); for (let crate of crates) { if (currentWeight + crate[1] > 27) { result.push(currentPorter); currentPorter = [crate[0]]; currentWeight = crate[1]; } else { currentPorter.push(crate[0]); currentWeight += crate[1]; } } if (currentPorter.length > 0) { result.push(currentPorter); } return result; }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.