2463. Minimum Total Distance Traveled
Difficulty: Hard
Topics: Array
, Dynamic Programming
, Sorting
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.
The positions of each robot are unique. The positions of each factory are also unique. Note that a robot can be in the same position as a factory initially.
All the robots are initially broken; they keep moving in one direction. The direction could be the negative or the 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.
At any moment, you can set the initial direction of moving for some robot. Your target is to minimize the total distance traveled by all the robots.
Return the minimum total distance traveled by all the robots. The test cases are generated such that all the robots can be repaired.
Note that
- All robots move at the same speed.
- If two robots move in the same direction, they will never collide.
- If two robots move in opposite directions and they meet at some point, they do not collide. They cross each other.
- If a robot passes by a factory that reached its limits, it crosses it as if it does not exist.
- If the robot moved from a position
x
to a positiony
, the distance it moved is|y - x|
.
Example 1:
- Input: robot = [0,4,6], factory = [[2,2],[6,2]]
- Output: 4
-
Explanation: As shown in the figure:
- The first robot at position 0 moves in the positive direction. It will be repaired at the first factory.
- The second robot at position 4 moves in the negative direction. It will be repaired at the first factory.
- The third robot at position 6 will be repaired at the second factory. It does not need to move.
- The limit of the first factory is 2, and it fixed 2 robots.
- The limit of the second factory is 2, and it fixed 1 robot.
- The total distance is |2 - 0| + |2 - 4| + |6 - 6| = 4. It can be shown that we cannot achieve a better total distance than 4.
Example 2:
- Input: robot = [1,-1], factory = [[-2,1],[2,1]]
- Output: 2
-
Explanation: As shown in the figure:
- The first robot at position 1 moves in the positive direction. It will be repaired at the second factory.
- The second robot at position -1 moves in the negative direction. It will be repaired at the first factory.
- The limit of the first factory is 1, and it fixed 1 robot.
- The limit of the second factory is 1, and it fixed 1 robot.
- The total distance is |2 - 1| + |(-2) - (-1)| = 2. It can be shown that we cannot achieve a better total distance than 2.
Constraints:
1 <= robot.length, factory.length <= 100
factory[j].length == 2
-109 <= robot[i], positionj <= 109
0 <= limitj <= robot.length
- The input will be generated such that it is always possible to repair every robot.
Hint:
- Sort robots and factories by their positions.
- After sorting, notice that each factory should repair some subsegment of robots.
- Find the minimum total distance to repair first i robots with first j factories.
Solution:
We can use dynamic programming with sorted robot
and factory
arrays. The idea is to minimize the distance each robot must travel to be repaired by a factory, respecting each factory’s repair capacity. Here’s a step-by-step breakdown of the approach:
Sort the
robot
andfactory
arrays by position. Sorting helps in minimizing the travel distance as we can assign nearby robots to nearby factories.-
Dynamic Programming Approach: We define a 2D DP table
dp[i][j]
where:-
i
represents the firsti
robots. -
j
represents the firstj
factories. -
dp[i][j]
stores the minimum total distance for repairing thesei
robots using thesej
factories.
-
-
State Transition:
- For each factory, try to repair a subset of consecutive robots within its limit.
- For a factory
j
at positionp
, calculate the minimum distance required for assigningk
robots to it by summing the distances from each robot to the factory's position. - Update the DP state by selecting the minimum between repairing fewer robots or utilizing the factory capacity to the fullest.
Let's implement this solution in PHP: 2463. Minimum Total Distance Traveled
<?php
/**
* @param Integer[] $robot
* @param Integer[][] $factory
* @return Integer
*/
function minimumTotalDistance($robot, $factory) {
...
...
...
/**
* go to ./solution.php
*/
}
// Test cases
$robot = [0, 4, 6];
$factory = [[2, 2], [6, 2]];
echo minimumTotalDistance($robot, $factory); // Output: 4
$robot = [1, -1];
$factory = [[-2, 1], [2, 1]];
echo minimumTotalDistance($robot, $factory); // Output: 2
?>
Explanation:
-
Sorting: We sort
robot
andfactory
by positions to ensure we assign nearby robots to nearby factories. -
DP Initialization: Initialize
dp[0][0] = 0
since no robots repaired by no factories means zero distance. -
Dynamic Programming Transition:
- For each factory
j
, we try repairing thek
robots preceding it within its limit. - The total distance is accumulated in
sumDist
. - We update
dp[i][j]
with the minimum value after repairingk
robots, considering the distance and previous states.
- For each factory
Complexity
-
Time Complexity:
O(n * m * L)
wheren
is the number of robots,m
is the number of factories, andL
is the maximum limit of repairs any factory can handle. -
Space Complexity:
O(n * m)
for the DP table.
This solution efficiently calculates the minimum travel distance for all robots to be repaired within their factory limits.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)