2463. Minimum Total Distance Traveled

/**
 * Problem: LeetCode 2463 - Minimum Total Distance Traveled
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
        Collections.sort(robot);
        Arrays.sort(factory, (a, b) -> Integer.compare(a[0], b[0]));

        int n = robot.size();
        int m = factory.length;
        long INF = (long) 1e16;

        long[] dp = new long[n + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int j = 0; j < m; j++) {
            long pos = factory[j][0];
            int limit = factory[j][1];
            long[] nextDp = Arrays.copyOf(dp, n + 1);

            for (int i = 1; i <= n; i++) {
                long cost = 0;
                for (int k = 1; k <= Math.min(i, limit); k++) {
                    cost += Math.abs(robot.get(i - k) - pos);
                    if (dp[i - k] != INF) {
                        nextDp[i] = Math.min(nextDp[i], dp[i - k] + cost);
                    }
                }
            }
            dp = nextDp;
        }

        return dp[n];
    }
}

"""
Problem: LeetCode 2463 - Minimum Total Distance Traveled
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        robot.sort()
        factory.sort(key=lambda f: f[0])

        n = len(robot)
        m = len(factory)
        INF = float('inf')

        dp = [INF] * (n + 1)
        dp[0] = 0

        for pos, limit in factory:
            next_dp = list(dp)
            for i in range(1, n + 1):
                cost = 0
                for k in range(1, min(i, limit) + 1):
                    cost += abs(robot[i - k] - pos)
                    if dp[i - k] != INF:
                        next_dp[i] = min(next_dp[i], dp[i - k] + cost)
            dp = next_dp

        return dp[n]

/**
 * Problem: LeetCode 2463 - Minimum Total Distance Traveled
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });

        int n = robot.size();
        int m = factory.size();
        long long INF = 1e16;

        vector<long long> dp(n + 1, INF);
        dp[0] = 0;

        for (int j = 0; j < m; j++) {
            long long pos = factory[j][0];
            int limit = factory[j][1];
            vector<long long> nextDp = dp;

            for (int i = 1; i <= n; i++) {
                long long cost = 0;
                for (int k = 1; k <= min(i, limit); k++) {
                    cost += abs(robot[i - k] - pos);
                    if (dp[i - k] != INF) {
                        nextDp[i] = min(nextDp[i], dp[i - k] + cost);
                    }
                }
            }
            dp = nextDp;
        }

        return dp[n];
    }
};

/**
 * Problem: LeetCode 2463 - Minimum Total Distance Traveled
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[]} robot
 * @param {number[][]} factory
 * @return {number}
 */
var minimumTotalDistance = function(robot, factory) {
    robot.sort((a, b) => a - b);
    factory.sort((a, b) => a[0] - b[0]);

    const n = robot.length;
    const m = factory.length;
    const INF = 1e16;

    let dp = new Float64Array(n + 1).fill(INF);
    dp[0] = 0;

    for (let j = 0; j < m; j++) {
        const [pos, limit] = factory[j];
        const nextDp = new Float64Array(dp);

        for (let i = 1; i <= n; i++) {
            let cost = 0;
            for (let k = 1; k <= Math.min(i, limit); k++) {
                cost += Math.abs(robot[i - k] - pos);
                if (dp[i - k] !== INF) {
                    nextDp[i] = Math.min(nextDp[i], dp[i - k] + cost);
                }
            }
        }
        dp = nextDp;
    }

    return dp[n];
};