We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Total Distance Traveled

Number: 2554

Difficulty: Hard

Paid? No

Companies: Bloomberg, Infosys

Problem Description

Given positions of broken robots and factories (each factory has a repair limit), determine the minimum total distance the robots must travel so that each robot is repaired. A robot can be directed to move in one of the two directions along the X-axis, and when it reaches a factory that hasn’t reached its repair limit, it gets fixed. The goal is to assign robots to factories such that the sum of their moving distances is minimized.

Key Insights

  • Sort the robot positions and the factory positions.
  • Use dynamic programming to decide how many robots to assign to each factory.
  • For each factory, iterate from 0 to its repair limit (ensuring you don’t assign more robots than available) and calculate the cost of moving the robots from their positions to the factory.
  • Recursively combine the choices across factories to find the optimal solution.
  • Memoization (or iterative DP) avoids redundant computations by reusing sub-problem solutions.

Space and Time Complexity

Time Complexity: O(R * F * L) where R is the number of robots, F is the number of factories, and L is the maximum limit per factory. Space Complexity: O(R * F) for storing the DP results (plus additional recursion stack space if using recursion).

Solution

We first sort both the robot and factory arrays. Then, we define a DP function dp(i, j) where i is the index of the current robot to assign and j is the index of the current factory being considered. In dp(i, j), we try every possible number of robots (from 0 up to the current factory’s repair limit, as long as we have enough remaining robots) to assign to the factory j. For each possible assignment, we compute the total cost as the sum of distances from each assigned robot to the factory position plus the optimal solution for the remaining robots and factories. We memoize the results to ensure efficiency.

Code Solutions

import math
from functools import lru_cache

def minimumTotalDistance(robot, factory):
    # Sort the robot and factory arrays based on positions.
    robot.sort()
    factory.sort(key=lambda x: x[0])
    n = len(robot)
    m = len(factory)
    
    # Use memoization to store results of subproblems.
    @lru_cache(maxsize=None)
    def dp(robot_index, factory_index):
        # If all robots are assigned, no additional cost.
        if robot_index == n:
            return 0
        # If no factory left to assign but robots are still remaining, return a large number.
        if factory_index == m:
            return math.inf
        
        # Unpack current factory info.
        factory_pos, limit = factory[factory_index]
        result = math.inf
        current_cost = 0
        
        # Try assigning t robots (from 0 to limit) to the current factory.
        # t=0 means skip the current factory.
        for t in range(0, limit + 1):
            # Ensure that we don't assign more robots than available.
            if robot_index + t > n: 
                break
            # For each robot assigned to the current factory, accumulate the distance cost.
            if t > 0:
                # robot_index + t - 1 is the last assigned robot.
                current_cost += abs(robot[robot_index + t - 1] - factory_pos)
            # Calculate total cost as current assignment cost plus optimal cost for remaining robots and next factory.
            result = min(result, current_cost + dp(robot_index + t, factory_index + 1))
        return result
    
    return dp(0, 0)

# Example usage:
print(minimumTotalDistance([0,4,6], [[2,2],[6,2]]))  # Output: 4
← Back to All Questions