Jungle Expedition Resupply — Problem Statement & Solution Guide

GreedyMediumMixed

TimeO(N log N + M log M)

SpaceO(1) additional

Problem Description

During a jungle expedition, a set of trekkers are positioned along a straight line. Each trekker i is located at coordinate p_i and requires d_i units of supplies. A number of supply packages have been airdropped; package j is at coordinate s_j and contains q_j units. A package can be split arbitrarily among any number of trekkers, but a unit of supply can travel only from its drop point to a trekker’s location, incurring a cost equal to the absolute distance between the two points. The expedition leader must decide how many units each package should deliver to each trekker so that every trekker’s demand is satisfied while the total travel cost is minimized. If the combined quantity of all packages is insufficient to meet the total demand, the task is impossible.

Input:

- The first line contains two integers N and M – the number of trekkers and the number of supply packages.

- The next N lines each contain two integers p_i and d_i – the position of the i‑th trekker and the amount of supplies it needs.

- The following M lines each contain two integers s_j and q_j – the position of the j‑th package and the amount of supplies it carries.

Output:

- Print a single integer – the minimum possible total travel cost. If the demands cannot be fulfilled, print -1.

The optimal allocation can be obtained by processing trekkers and packages in order of their coordinates and greedily matching the nearest available supply to the current unmet demand.

DSA Pattern Breakdown

"Jungle Expedition Resupply"

medium

WHY DOES IT MATTER?

This pattern exemplifies greedy matching on a line, a cornerstone for many logistics, load‑balancing, and inventory‑replenishment problems where the cost metric is linear distance. Mastering it equips engineers to design optimal, low‑latency routing and resource allocation systems.

OPTIMIZATION CHALLENGE

The key insight is that crossing flows can always be untangled to reduce total distance, which means the optimal solution never needs to consider non‑adjacent pairings. This reduces the problem from combinatorial (potentially O(N·M) assignments) to a linear scan.

REAL-WORLD CONNECTION

Think of a warehouse with pallets (supply) and retail stores (demand) along a highway. The cheapest way to ship goods is to load the nearest truck with the nearest store's order, never sending a truck past another store that still needs stock, mirroring the two‑pointer sweep.

During the interview, implement the solution with two sorted arrays and two indices. Keep a running variable for remaining supply/demand, update cost with a 64‑bit integer, and remember to handle large quantities by using long long (or Python int). Edge‑case handling (zero‑quantity entries) often trips candidates.

COMPLEXITY AT A GLANCE

⏱ Time:O(N log N + M log M)

💾 Space:O(1) additional

Core Theory — Why This Approach?

The Jungle Expedition Resupply problem is a classic instance of a one‑dimensional transportation problem. When both trekkers (demands) and supply packages are placed on a line, the optimal way to move units is to match the leftmost unmet demand with the leftmost available supply, because any crossing of flows would increase total distance. A naive solution would try every possible assignment, leading to exponential blow‑up, or would simulate each unit individually, resulting in O(totalUnits) time which is infeasible when q_j and d_i can be up to 10^9. The optimal paradigm uses a two‑pointer greedy sweep: after sorting both lists by coordinate, we repeatedly transfer as much as possible from the current supply to the current demand, accumulating cost as amount × |s_j − p_i|. This works because the cost function is linear and the line imposes a total order, guaranteeing that the greedy local choice is globally optimal.

Interview Questions on This Problem

Q1How would you modify the algorithm if each unit of supply could only travel a maximum distance K from its drop point?

Introduce a feasibility check while sweeping: when the distance between the current supply and demand exceeds K, the supply cannot serve that demand, so you must skip to the next supply that is within K. If no such supply exists, the instance is impossible. The rest of the greedy matching stays the same, but you must maintain a window of supplies that are still reachable.

Q2Can the problem be solved using a prefix‑sum approach instead of two pointers? Explain the relationship.

Yes. After sorting, compute the cumulative net supply (supply − demand) at each position. The minimum total distance equals the sum of absolute values of these prefix sums, which is equivalent to the two‑pointer greedy because each unit crossing a point contributes exactly one to the prefix sum magnitude. This insight shows the equivalence between flow matching and prefix‑sum balancing.

Q3What changes are required if supplies can be split only among at most two trekkers?

The greedy matching still works, but you must enforce a counter per package tracking how many distinct demand nodes it has been assigned to. When a package has already served two trekkers, you must move to the next package even if it still has leftover quantity. This adds O(1) bookkeeping per transfer without affecting overall O(N+M) complexity.

Examples

Example 1

Input

Output

Explanation: Step‑by‑step: allocate nearest available supply greedily, compute distance·units for each transfer, sum to obtain 18.

Example 2

Input

Output

-1

Explanation: Total demand = 4+2+1 = 7, but the single package provides only 5 units. Since supply < demand, fulfilling all trekkers is impossible, so the answer is -1.

Example 3

Input

Output

Explanation: Greedy left‑to‑right matching yields the minimum total distance of 50.

Constraints

1 <= N, M <= 100000
0 <= p_i, s_j <= 10^9
1 <= d_i, q_j <= 10^9
The sum of all d_i and q_j fits in a 64‑bit signed integer

Optimal Approach & Strategy

Sort both lists and greedily match the nearest available supply with the nearest unmet demand using two pointers, accumulating distance × amount.

Brute Force Approach

Try every possible way to assign each unit of supply to a trekker, computing total distance for each assignment.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N log N + M log M)

function solve(trekkers, packages) {
    let totalDemand = trekkers.reduce((s, t) => s + t[1], 0);
    let totalSupply = packages.reduce((s, p) => s + p[1], 0);
    if (totalSupply < totalDemand) return -1;

    trekkers.sort((a, b) => a[0] - b[0]);
    packages.sort((a, b) => a[0] - b[0]);

    let totalCost = 0;
    let tIdx = 0, pIdx = 0;
    let tDemand = trekkers[0] ? trekkers[0][1] : 0;
    let pSupply = packages[0] ? packages[0][1] : 0;

    while (tIdx < trekkers.length && pIdx < packages.length) {
        let transfer = Math.min(tDemand, pSupply);
        totalCost += transfer * Math.abs(trekkers[tIdx][0] - packages[pIdx][0]);
        tDemand -= transfer;
        pSupply -= transfer;
        if (tDemand === 0) {
            tIdx++;
            if (tIdx < trekkers.length) tDemand = trekkers[tIdx][1];
        }
        if (pSupply === 0) {
            pIdx++;
            if (pIdx < packages.length) pSupply = packages[pIdx][1];
        }
    }
    return totalCost;
}

#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
using namespace std;

class Solution {
public:
    long long solve(vector<pair<long long, long long>>& trekkers, vector<pair<long long, long long>>& packages) {
        long long totalDemand = 0;
        for (const auto& t : trekkers) totalDemand += t.second;
        long long totalSupply = 0;
        for (const auto& p : packages) totalSupply += p.second;
        if (totalSupply < totalDemand) return -1;

        sort(trekkers.begin(), trekkers.end());
        sort(packages.begin(), packages.end());

        long long totalCost = 0;
        size_t tIdx = 0, pIdx = 0;
        long long tDemand = (trekkers.empty() ? 0 : trekkers[0].second);
        long long pSupply = (packages.empty() ? 0 : packages[0].second);

        while (tIdx < trekkers.size() && pIdx < packages.size()) {
            long long transfer = min(tDemand, pSupply);
            totalCost += transfer * abs(trekkers[tIdx].first - packages[pIdx].first);
            tDemand -= transfer;
            pSupply -= transfer;
            if (tDemand == 0) {
                tIdx++;
                if (tIdx < trekkers.size()) tDemand = trekkers[tIdx].second;
            }
            if (pSupply == 0) {
                pIdx++;
                if (pIdx < packages.size()) pSupply = packages[pIdx].second;
            }
        }
        return totalCost;
    }
};

import java.util.*;

public class Solution {
    public long solve(long[][] trekkers, long[][] packages) {
        long totalDemand = 0;
        for (long[] t : trekkers) totalDemand += t[1];
        long totalSupply = 0;
        for (long[] p : packages) totalSupply += p[1];
        if (totalSupply < totalDemand) return -1;

        Arrays.sort(trekkers, Comparator.comparingLong(a -> a[0]));
        Arrays.sort(packages, Comparator.comparingLong(a -> a[0]));

        long totalCost = 0;
        int tIdx = 0, pIdx = 0;
        long tDemand = trekkers.length > 0 ? trekkers[0][1] : 0;
        long pSupply = packages.length > 0 ? packages[0][1] : 0;

        while (tIdx < trekkers.length && pIdx < packages.length) {
            long transfer = Math.min(tDemand, pSupply);
            totalCost += transfer * Math.abs(trekkers[tIdx][0] - packages[pIdx][0]);
            tDemand -= transfer;
            pSupply -= transfer;
            if (tDemand == 0) {
                tIdx++;
                if (tIdx < trekkers.length) tDemand = trekkers[tIdx][1];
            }
            if (pSupply == 0) {
                pIdx++;
                if (pIdx < packages.length) pSupply = packages[pIdx][1];
            }
        }
        return totalCost;
    }
}

def solve(trekkers: list[tuple[int, int]], packages: list[tuple[int, int]]) -> int:
    total_demand = sum(t[1] for t in trekkers)
    total_supply = sum(p[1] for p in packages)
    if total_supply < total_demand:
        return -1

    trekkers = sorted(trekkers, key=lambda x: x[0])
    packages = sorted(packages, key=lambda x: x[0])

    total_cost = 0
    t_idx = 0
    p_idx = 0
    t_demand = trekkers[0][1] if trekkers else 0
    p_supply = packages[0][1] if packages else 0

    while t_idx < len(trekkers) and p_idx < len(packages):
        transfer = min(t_demand, p_supply)
        total_cost += transfer * abs(trekkers[t_idx][0] - packages[p_idx][0])
        t_demand -= transfer
        p_supply -= transfer
        if t_demand == 0:
            t_idx += 1
            if t_idx < len(trekkers):
                t_demand = trekkers[t_idx][1]
        if p_supply == 0:
            p_idx += 1
            if p_idx < len(packages):
                p_supply = packages[p_idx][1]
    return total_cost

function solve(trekkers, packages) {
    let totalDemand = trekkers.reduce((s, t) => s + t[1], 0);
    let totalSupply = packages.reduce((s, p) => s + p[1], 0);
    if (totalSupply < totalDemand) return -1;

    trekkers.sort((a, b) => a[0] - b[0]);
    packages.sort((a, b) => a[0] - b[0]);

    let totalCost = 0;
    let tIdx = 0, pIdx = 0;
    let tDemand = trekkers[0] ? trekkers[0][1] : 0;
    let pSupply = packages[0] ? packages[0][1] : 0;

    while (tIdx < trekkers.length && pIdx < packages.length) {
        let transfer = Math.min(tDemand, pSupply);
        totalCost += transfer * Math.abs(trekkers[tIdx][0] - packages[pIdx][0]);
        tDemand -= transfer;
        pSupply -= transfer;
        if (tDemand === 0) {
            tIdx++;
            if (tIdx < trekkers.length) tDemand = trekkers[tIdx][1];
        }
        if (pSupply === 0) {
            pIdx++;
            if (pIdx < packages.length) pSupply = packages[pIdx][1];
        }
    }
    return totalCost;
}

Asked in Top Tech Interviews

uncategorizedmediumgeneric

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.

Jungle Expedition Resupply Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Greedy

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Jungle Expedition Resupply — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor