382. Minimum Total Distance Traveled

After sorting both robots and factories by position, the optimal matching has a non-crossing property: if robot A (left of robot B) goes to a factory to its right, swapping their assignments can never increase total distance — so we can assume robots map to factory slots in the same sorted order. That collapses the problem to a 1-D matching DP over sorted positions.

Why a non-crossing matching is optimal

Imagine robot A is left of robot B, and we assign A to a factory Y to the right while B goes to factory X to the left, crossing their paths. If we swap them — A → X, B → Y — the total distance never increases. (This is the classic exchange argument for matching points on a line.) So an optimal solution always has robots paired to factories in sorted order.

Expanding factories into slots

Each factory (position, limit) can absorb up to limit robots. Expand it into limit copies of its position — now each "slot" can hold at most one robot, and we can think of the problem as matching n robots to a subset of m slots in sorted order.

DP

Define dp[i][j] = minimum total distance after assigning the first i robots using the first j slots. Transitions for i ≥ 1, j ≥ i:

• Skip slot j: dp[i][j] = dp[i][j - 1]. We use the same i robots in j - 1 slots.
• Match robot i with slot j: dp[i][j] = dp[i - 1][j - 1] + |robots[i-1] - slots[j-1]|.

Take the minimum of the two. Base cases: dp[0][j] = 0 for all j (zero robots cost zero distance), dp[i][0] = ∞ for i > 0.

We need at least i slots for i robots, so the inner loop starts at j = i.

Steps

1. Sort robots ascending. Sort factories by position.
2. Build slots by expanding each factory: slots = [pos] * limit per factory, concatenated.
3. Initialise dp[0][*] = 0, everything else ∞.
4. Fill the table with the recurrence above.
5. Return dp[n][m].

Walk-through (small example)

robots = [0, 4, 6], factories = [[2, 2], [6, 2]].

Sorted positions: robots [0, 4, 6], slots [2, 2, 6, 6]. So n = 3, m = 4.

(Compute each cell as min(dp[i][j-1], dp[i-1][j-1] + |robots[i-1] - slots[j-1]|).)

Answer: dp[3][4] = 4. The matching: robot 0 → slot 2 (dist 2), robot 4 → slot 6 (dist 2), robot 6 → slot 6 (dist 0). Total: 4.

Edge cases

• Total slots < robots: the problem guarantees feasibility, but our DP would return ∞ (the inner loop never reaches dp[n][m] if m < n).
• All factories at one position: the DP collapses, all robots take that factory, distances sum to sum(|robot - pos|).

Complexity

• Time: O(n · m) — fill the DP table.
• Space: O(n · m) — the DP table. Could be reduced to O(m) by keeping only the previous row.

import java.util.*;

class Solution {
    public long minimumTotalDistance(List<Integer> robots, int[][] factories) {
        Collections.sort(robots);
        Arrays.sort(factories, (a, b) -> Integer.compare(a[0], b[0]));
        List<Integer> slots = new ArrayList<>();
        for (int[] f : factories) {
            for (int i = 0; i < f[1]; i++) {
                slots.add(f[0]);
            }
        }
        int n = robots.size(), m = slots.size();
        long INF = Long.MAX_VALUE / 2;
        long[][] dp = new long[n + 1][m + 1];
        for (long[] row : dp) Arrays.fill(row, INF);
        for (int j = 0; j <= m; j++) dp[0][j] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= m; j++) {
                dp[i][j] = dp[i][j - 1];
                long cost = dp[i - 1][j - 1] + Math.abs(robots.get(i - 1) - slots.get(j - 1));
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
        return dp[n][m];
    }
}