Minimum Total Distance Traveled

hard dynamic programming sorting array

Problem

Broken robots and factories sit on the X-axis. robot[i] is a robot's position; factory[j] = [position, limit] is a factory that can repair at most limit robots. Every robot moves left or right (you choose) until it reaches a factory with free capacity, where it stops. The distance a robot travels is the absolute gap between its start and the factory. Return the minimum total distance travelled by all robots so that every robot is repaired.

Inputrobot = [0,4,6], factory = [[2,2],[6,2]]

Output4

Robot 0 → factory at 2 (dist 2), robot 4 → factory at 2 (dist 2), robot 6 → factory at 6 (dist 0). Total = 4.

Inputrobot = [1,-1], factory = [[-2,1],[2,1]]

Output2

Robot 1 → factory at 2 (dist 1), robot -1 → factory at -2 (dist 1). Total = 2.

robot (comma-separated)

factory (pos:limit, comma-separated)

def minimumTotalDistance(robot, factory):
    robot.sort()
    factory.sort()
    m, n = len(robot), len(factory)
    INF = float("inf")
    dp = [[INF] * (m + 1) for _ in range(n + 1)]
    for j in range(n + 1):
        dp[j][m] = 0
    for j in range(n - 1, -1, -1):
        pos, lim = factory[j]
        for i in range(m - 1, -1, -1):
            best = dp[j + 1][i]
            cost = 0
            for k in range(1, lim + 1):
                if i + k > m:
                    break
                cost += abs(robot[i + k - 1] - pos)
                if dp[j + 1][i + k] < INF:
                    best = min(best, cost + dp[j + 1][i + k])
            dp[j][i] = best
    return dp[0][0]

function minimumTotalDistance(robot, factory) {
  robot.sort((a, b) => a - b);
  factory.sort((a, b) => a[0] - b[0]);
  const m = robot.length, n = factory.length, INF = Infinity;
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(INF));
  for (let j = 0; j <= n; j++) dp[j][m] = 0;
  for (let j = n - 1; j >= 0; j--) {
    const pos = factory[j][0], lim = factory[j][1];
    for (let i = m - 1; i >= 0; i--) {
      let best = dp[j + 1][i], cost = 0;
      for (let k = 1; k <= lim && i + k <= m; k++) {
        cost += Math.abs(robot[i + k - 1] - pos);
        if (dp[j + 1][i + k] < INF)
          best = Math.min(best, cost + dp[j + 1][i + k]);
      }
      dp[j][i] = best;
    }
  }
  return dp[0][0];
}

long minimumTotalDistance(int[] robot, int[][] factory) {
    Arrays.sort(robot);
    Arrays.sort(factory, (a, b) -> a[0] - b[0]);
    int m = robot.length, n = factory.length;
    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 <= n; j++) dp[j][m] = 0;
    for (int j = n - 1; j >= 0; j--) {
        int pos = factory[j][0], lim = factory[j][1];
        for (int i = m - 1; i >= 0; i--) {
            long best = dp[j + 1][i], cost = 0;
            for (int k = 1; k <= lim && i + k <= m; k++) {
                cost += Math.abs(robot[i + k - 1] - pos);
                best = Math.min(best, cost + dp[j + 1][i + k]);
            }
            dp[j][i] = best;
        }
    }
    return dp[0][0];
}

long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
    sort(robot.begin(), robot.end());
    sort(factory.begin(), factory.end());
    int m = robot.size(), n = factory.size();
    long long INF = 1e18;
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, INF));
    for (int j = 0; j <= n; j++) dp[j][m] = 0;
    for (int j = n - 1; j >= 0; j--) {
        int pos = factory[j][0], lim = factory[j][1];
        for (int i = m - 1; i >= 0; i--) {
            long long best = dp[j + 1][i], cost = 0;
            for (int k = 1; k <= lim && i + k <= m; k++) {
                cost += abs(robot[i + k - 1] - pos);
                best = min(best, cost + dp[j + 1][i + k]);
            }
            dp[j][i] = best;
        }
    }
    return dp[0][0];
}

Explanation

Sort both the robots and the factories by position. Once everything is in left-to-right order, an optimal assignment never has its "wires" cross: a contiguous block of robots is sent to each factory. That is the key insight that turns a hard matching problem into a clean dynamic program.

Define dp[j][i] as the minimum total distance to repair robots i, i+1, …, m-1 using only factories j, j+1, …, n-1. The answer is dp[0][0] — all robots, all factories available.

We fill the table from the bottom-right. The base case is dp[j][m] = 0 for every j: when no robots remain, the cost is zero. Any state with robots left but no factories left stays at infinity (unreachable).

For each factory j and starting robot i, we choose how many robots k (from 0 up to the factory's limit) this factory repairs. Skipping the factory gives dp[j+1][i]; assigning the next k robots costs the sum of their distances to pos plus dp[j+1][i+k]. We keep the smallest.

The running cost is built incrementally as k grows, so each transition adds only one absolute-difference term. With m robots, n factories, and limits bounded by m, the whole table fills in O(m·n·m) time.

Time: O(m · n · m) Space: O(m · n)