2463. Minimum Total Distance Traveled Hard

1/**
2 * [2463] Minimum Total Distance Traveled
3 *
4 * 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] = [positionj, limitj] indicates that positionj is the position of the j^th factory and that the j^th factory can repair at most limitj robots.
5 * 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.
6 * 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.
7 * 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.
8 * Return the minimum total distance traveled by all the robots. The test cases are generated such that all the robots can be repaired.
9 * Note that
10 * 
11 * 	All robots move at the same speed.
12 * 	If two robots move in the same direction, they will never collide.
13 * 	If two robots move in opposite directions and they meet at some point, they do not collide. They cross each other.
14 * 	If a robot passes by a factory that reached its limits, it crosses it as if it does not exist.
15 * 	If the robot moved from a position x to a position y, the distance it moved is |y - x|.
16 * 
17 *  
18 * <strong class="example">Example 1:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2022/09/15/example1.jpg" style="width: 500px; height: 320px;" />
20 * Input: robot = [0,4,6], factory = [[2,2],[6,2]]
21 * Output: 4
22 * Explanation: As shown in the figure:
23 * - The first robot at position 0 moves in the positive direction. It will be repaired at the first factory.
24 * - The second robot at position 4 moves in the negative direction. It will be repaired at the first factory.
25 * - The third robot at position 6 will be repaired at the second factory. It does not need to move.
26 * The limit of the first factory is 2, and it fixed 2 robots.
27 * The limit of the second factory is 2, and it fixed 1 robot.
28 * 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.
29 * 
30 * <strong class="example">Example 2:
31 * <img alt="" src="https://assets.leetcode.com/uploads/2022/09/15/example-2.jpg" style="width: 500px; height: 329px;" />
32 * Input: robot = [1,-1], factory = [[-2,1],[2,1]]
33 * Output: 2
34 * Explanation: As shown in the figure:
35 * - The first robot at position 1 moves in the positive direction. It will be repaired at the second factory.
36 * - The second robot at position -1 moves in the negative direction. It will be repaired at the first factory.
37 * The limit of the first factory is 1, and it fixed 1 robot.
38 * The limit of the second factory is 1, and it fixed 1 robot.
39 * The total distance is |2 - 1| + |(-2) - (-1)| = 2. It can be shown that we cannot achieve a better total distance than 2.
40 * 
41 *  
42 * Constraints:
43 * 
44 * 	1 <= robot.length, factory.length <= 100
45 * 	factory[j].length == 2
46 * 	-10^9 <= robot[i], positionj <= 10^9
47 * 	0 <= limitj <= robot.length
48 * 	The input will be generated such that it is always possible to repair every robot.
49 * 
50 */
51pub struct Solution {}
52
53// problem: https://leetcode.com/problems/minimum-total-distance-traveled/
54// discuss: https://leetcode.com/problems/minimum-total-distance-traveled/discuss/?currentPage=1&orderBy=most_votes&query=
55
56// submission codes start here
57
58impl Solution {
59    pub fn minimum_total_distance(robot: Vec<i32>, factory: Vec<Vec<i32>>) -> i64 {
60        
61    }
62}
63
64// submission codes end
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn test_2463() {
72    }
73}
74