diff options
Diffstat (limited to 'min_total_distance_traveled.py')
-rw-r--r-- | min_total_distance_traveled.py | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/min_total_distance_traveled.py b/min_total_distance_traveled.py new file mode 100644 index 0000000..30a3172 --- /dev/null +++ b/min_total_distance_traveled.py @@ -0,0 +1,43 @@ +# 2463. Minimum Total Distance Traveled + +""" +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 i'th robot. you are +also given a 2d integer array 'factory' where 'factory[j] = [position_i, +limit_i]' indicates that 'position[j]' is the position of the j'th factory +and that the j'th factory can repair at most 'limit[j]' robots. the positions +of each robot are unique. note that a robot can be in the same position as a +factory initially. all the robots are initially broke; they keep moving in +one direction. the direction could be the negative or positive direction of +the x-axis. when a robot reaches a factory that did not reach its limit, the +factory repairs the robot and it stops moving. return the minimum total +distance traveled by all the robots. the test cases are generated as such +that all the robots can be repaired. +""" + + +class Solution(object): + def minimumTotalDistance(self, robot, factory): + """ + :type robot: List[int] + :type factory: List[List[int]] + :rtype: int + """ + n, m = len(robot), len(factory) + dp = [float("inf")] * (n + 1) + dp[n] = 0 + robot.sort() + factory.sort() + for j in range(m - 1, -1, -1): + for i in range(n): + curr = 0 + for k in range(1, min(factory[j][1], n - i) + 1): + curr += abs(robot[i + k - 1] - factory[j][0]) + dp[i] = min(dp[i], dp[i + k] + curr) + return dp[0] + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumTotalDistance(robot=[0, 4, 6], factory=[[2, 2], [6, 2]])) + print(obj.minimumTotalDistance(robot=[1, -1], factory=[[-2, 1], [2, 1]])) |