Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

On a line, crossing robot-to-factory assignments can be uncrossed without increasing total distance. Thus some optimum matches sorted robots to sorted capacity slots in order. Expanding each factory into one slot per repair capacity turns the problem into selecting which slots to use.

Approach

Sort robots and factories, then repeat each factory position by its capacity. Let dp[i][j] be the minimum distance for the first i robots using the first j slots. Initialize zero robots to cost zero and impossible states to infinity. Either skip slot j, or assign robot i to it and add their distance to dp[i - 1][j - 1]. Return the state covering all robots and slots. Each slot is used at most once, enforcing capacities.

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

        for pos, limit in factory:
            slots += [pos] * limit

        m, n = len(robot), len(slots)
        dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]

        for j in range(n + 1):
            dp[0][j] = 0

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = min(
                    dp[i][j - 1], # skip slot
                    dp[i - 1][j - 1] + abs(robot[i - 1] - slots[j - 1]) # take slot
                )

        return dp[m][n]

Complexity analysis

Let R = robot.length, F = factory.length, and S be total capacity, the expanded slot count. Time is O(R log(R + 1) + F log(F + 1) + RS). Auxiliary space is O(RS + S + F), including the full DP table, expanded slots and sorting workspace. The F term matters when many factories have zero capacity; guaranteed feasibility gives S >= R >= 1.