aboutsummaryrefslogtreecommitdiff
path: root/min_total_distance_traveled.py
diff options
context:
space:
mode:
Diffstat (limited to 'min_total_distance_traveled.py')
-rw-r--r--min_total_distance_traveled.py43
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]]))