content: package codingquestions.leetcode;
  
  import java.util.ArrayDeque;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.Deque;
  import java.util.List;
  
  /**
   * 2463. Minimum Total Distance Traveled
   * Solved
   * Hard
   * Topics
   * Companies
   * Hint
   * 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.
   * <p>
   * 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.
   * <p>
   * 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.
   * <p>
   * 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.
   * <p>
   * Return the minimum total distance traveled by all the robots. The test cases are generated such that all the robots can be repaired.
   * <p>
   * Note that
   * <p>
   * 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 position y, the distance it moved is |y - x|.
   **/
  public class MinimumTotalDistanceTraveled {
      public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
          // Sort robots and factories by position for optimal assignment
          Collections.sort(robot);
          Arrays.sort(factory, (a, b) -> Integer.compare(a[0], b[0]));
  
          int m = robot.size();
          int n = factory.length;
  
          // dp[i][j] represents min total distance for robots[i:] using factories[j:]
          long[][] dp = new long[m + 1][n + 1];
  
          // Set last column to MAX_VALUE as boundary condition
          for (int i = 0; i < m; i++) {
              dp[i][n] = Long.MAX_VALUE;
          }
  
          // Process each factory from right to left
          for (int j = n - 1; j >= 0; j--) {
              // Track cumulative distance from current factory to robots
              long prefix = 0;
              // Use deque to maintain potential optimal assignments
              Deque<Pair<Integer, Long>> qq = new ArrayDeque<>();
              // Initialize with boundary condition
              qq.offer(new Pair<>(m, 0L));
  
              // Process each robot from right to left
              for (int i = m - 1; i >= 0; i--) {
                  // Add distance from current robot to current factory
                  prefix += Math.abs(robot.get(i) - factory[j][0]);
  
                  // Remove assignments that exceed factory capacity
                  while (!qq.isEmpty() && qq.peekFirst().getKey() > i + factory[j][1]) {
                      qq.pollFirst();
                  }
  
                  // Remove suboptimal assignments
                  while (!qq.isEmpty() && qq.peekLast().getValue() >= dp[i][j + 1] - prefix) {
                      qq.pollLast();
                  }
  
                  // Add current state to deque
                  qq.offerLast(new Pair<>(i, dp[i][j + 1] - prefix));
                  // Update dp with optimal assignment
                  dp[i][j] = qq.peekFirst().getValue() + prefix;
              }
          }
  
          // Return minimum total distance for all robots
          return dp[0][0];
      }
  
      // Helper class to store key-value pairs
      private static class Pair<K, V> {
          private K key;
          private V value;
  
          public Pair(K key, V value) {
              this.key = key;
              this.value = value;
          }
  
          public K getKey() {
              return key;
          }
  
          public V getValue() {
              return value;
          }
      }
  }
  