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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Total Distance Traveled

Difficulty: Hard

Problem Description

There are some robots and factories on the X-axis. You are given an integer array robot where robot[i] is the position of the ith robot. You are also given a 2D integer array factory where factory[j] = [positionj, limitj] indicates that positionj is the position of the jth factory and that the jth factory can repair at most limitj robots.

All the robots are initially broken; they keep moving in one direction. When a robot reaches a factory that did not reach its limit, the factory repairs the robot, and it stops moving. Your target is to minimize the total distance traveled by all the robots. Return the minimum total distance traveled by all the robots.

Key Insights

  • Robots can move in either direction and can be directed to the nearest available factory.
  • Each factory has a repair limit, meaning it can only repair a certain number of robots.
  • The distance a robot travels to a factory is the absolute difference between their positions.
  • The problem can be approached using dynamic programming, where we track the minimum distance for subsets of robots and factories.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of robots and m is the number of factories.
Space Complexity: O(n) for storing the minimum distances up to each robot.

Solution

The solution involves using dynamic programming to efficiently track the minimum distance traveled by robots to factories. We create a DP table where each entry represents the minimum distance for the first i robots using the first j factories.

  1. Sort the robots and factories based on their positions to facilitate easier distance calculations.
  2. Initialize a DP table where dp[i][j] represents the minimum distance for the first i robots using the first j factories.
  3. Iterate through each robot and factory, updating the DP table based on the distances calculated.
  4. The final answer will be found in the last entry of the DP table.

Code Solutions

def minimumTotalDistance(robot, factory):
    robot.sort()
    factory.sort()
    n, m = len(robot), len(factory)
    
    # Initialize dp array
    dp = [[float('inf')] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = 0  # Base case: 0 robots and 0 factories = 0 distance

    for j in range(1, m + 1):
        dp[0][j] = 0  # 0 robots can be repaired by any number of factories with 0 distance
        
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # Calculate the distance for using the j-th factory
            total_distance = 0
            for k in range(1, factory[j - 1][1] + 1):  # k is the number of robots repaired by factory j-1
                if i - k >= 0:
                    total_distance += abs(robot[i - k] - factory[j - 1][0])
                    dp[i][j] = min(dp[i][j], dp[i - k][j - 1] + total_distance)
    
    return dp[n][m]
← Back to All Questions