Practice/Google/Leetcode 2463. Minimum Total Distance Traveled

Leetcode 2463. Minimum Total Distance Traveled

CodingMust

Problem

You are managing a robotic warehouse system where robots need to be assigned to distribution warehouses for maintenance. All robots and warehouses are positioned along a single number line.

Given:

• An array robots where robots[i] represents the position of the i-th robot on the number line
• An array warehouses where warehouses[j] = [position_j, capacity_j] indicates that warehouse j is located at position_j and can service at most capacity_j robots

Your task is to assign every robot to exactly one warehouse such that:

• No warehouse exceeds its service capacity
• The total distance traveled by all robots is minimized

The distance a robot travels is the absolute difference between its starting position and the warehouse position: |robot_position - warehouse_position|.

Return the minimum possible sum of distances traveled by all robots.

Requirements

1. Every robot must be assigned to exactly one warehouse
2. No warehouse can service more robots than its capacity allows
3. Minimize the total sum of absolute distances traveled
4. All positions are integers on a number line

Constraints

• 1 ≤ robots.length ≤ 100
• 1 ≤ warehouses.length ≤ 100
• warehouses[j].length == 2
• -109 ≤ robots[i], warehouses[j][0] ≤ 109
• 1 ≤ warehouses[j][1] ≤ 100
• All robot positions are unique
• All warehouse positions are unique
• The total capacity of all warehouses is at least the number of robots

Examples

Example 1:

` Input: robots = [0, 4, 6], warehouses = [[2, 2], [6, 2]] Output: 4 Explanation:

• Assign robots at positions 0 and 4 to the warehouse at position 2
  • Robot at 0 travels distance |0 - 2| = 2
  • Robot at 4 travels distance |4 - 2| = 2
• Assign robot at position 6 to the warehouse at position 6
  • Robot at 6 travels distance |6 - 6| = 0
• Total distance: 2 + 2 + 0 = 4 `

Example 2:

Input: robots = [1], warehouses = [[2, 1]] Output: 1 Explanation: The single robot travels from position 1 to warehouse at position 2, distance = 1.

Example 3:

Input: robots = [9, 11, 99, 101], warehouses = [[10, 1], [7, 1], [14, 1], [100, 1], [96, 1]] Output: 18 Explanation: Optimal assignment considers both proximity and capacity constraints.