Minimum Total Distance Traveled

Minimum Total Distance Traveled

What is this problem about?

The Minimum Total Distance Traveled problem gives you a list of robots on a number line and a list of factories, each with a position and capacity. Each robot must be assigned to a factory (within its capacity), and the cost is the absolute distance traveled. Minimize the total distance traveled by all robots. This hard Minimum Total Distance Traveled coding problem requires sorting and dynamic programming over the merged sorted sequence.

Why is this asked in interviews?

Microsoft, Infosys, Google, and Bloomberg ask this because it tests the optimal assignment of resources to facilities on a number line — a classic operations research problem. The key insight that sorting both robots and factories and then applying DP eliminates the need for complex matching algorithms. The array, sorting, and dynamic programming interview pattern is comprehensively tested.

Algorithmic pattern used

Sort both + DP. Sort robots by position. Expand factories into individual slots (a factory with capacity c at position p creates c separate "slots" at position p). Sort these slots. Now the problem reduces to: given sorted robots and sorted factory slots, find the optimal assignment where robot i is assigned to some slot j ≥ i (maintaining order). DP: dp[i][j] = minimum cost assigning first i robots to first j slots. Transition: assign robot i to slot j, or skip slot j. Final: dp[n][m].

Example explanation

Robots: [0, 4, 6]. Factory: (2, 1) capacity 1, (9, 1) capacity 1, (5, 1) capacity 1. Sort robots: [0, 4, 6]. Sort slots: [2, 5, 9].

• Assign robot 0 → slot 2: |0-2|=2. Robot 4 → slot 5: |4-5|=1. Robot 6 → slot 9: |6-9|=3. Total=6.
• Assign robot 0 → slot 2: 2. Robot 4 → slot 9: 5. Robot 6 → slot 5? Not valid (ordering must be preserved). Minimum total = 6.

Common mistakes candidates make

• Not sorting robots and factory slots before DP.
• Not expanding factories by capacity (treating a capacity-c factory as c individual slots).
• DP state indexing errors when robots and slots have different sizes.
• Trying to use greedy assignment without DP (greedy can fail with non-uniform factory positions).

Interview preparation tip

Assignment problems on a number line are almost always solved by sorting both sides and applying DP with an order-preserving constraint. The "expand factory capacity to individual slots" transformation is the key preprocessing step. After this, the DP structure is identical to sequence alignment or optimal matching DP. Practice 2D DP assignment problems — they form a recurring pattern in logistics optimization interviews at companies like Google and Bloomberg.