Minimum Total Distance Traveled Solution in C++

Ah, the classic dilemma of robots and factories! Imagine a world where robots are as lazy as your average couch potato, and they need to travel to factories to get fixed. But wait! These factories are not just around the corner; they are scattered all over the place. The challenge? Minimize the total distance traveled by these robots to get them back in shape. Sounds like a fun day out, right?

In this problem, we have a list of robots, each with a specific position, and a list of factories, each with a position and a limit on how many robots it can fix. The goal is to find the minimum total distance that all robots need to travel to get fixed.

Solution Links

Code Solution


class Solution {
 public:
  long long minimumTotalDistance(vector& robot,
                                 vector>& factory) {
    ranges::sort(robot);
    ranges::sort(factory);
    vector>> mem(
        robot.size(),
        vector>(factory.size(), vector(robot.size())));
    return minimumTotalDistance(robot, factory, 0, 0, 0, mem);
  }

 private:
  long minimumTotalDistance(const vector& robot,
                            const vector>& factory, int i, int j,
                            int k, vector>>& mem) {
    if (i == robot.size())
      return 0;
    if (j == factory.size())
      return LONG_MAX;
    if (mem[i][j][k] > 0)
      return mem[i][j][k];
    const long skipFactory =
        minimumTotalDistance(robot, factory, i, j + 1, 0, mem);
    const int position = factory[j][0];
    const int limit = factory[j][1];
    const long useFactory =
        limit > k ? minimumTotalDistance(robot, factory, i + 1, j, k + 1, mem) +
                        abs(robot[i] - position)
                  : LONG_MAX / 2;
    return mem[i][j][k] = min(skipFactory, useFactory);
  }
}

Approach Explanation

The code uses a recursive approach with memoization to solve the problem. It sorts both the robots and factories to ensure that we can efficiently calculate the minimum distance. The function minimumTotalDistance checks if all robots are fixed or if there are no factories left. If there are factories, it decides whether to skip the current factory or use it to fix a robot, updating the memoization table accordingly.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * m * n), where n is the number of robots and m is the number of factories.
Space Complexity	O(n * m * n) for the memoization table.

Real-World Example

Imagine a group of robots that need to get to a repair shop after a long day of work. Each robot is at a different location, and the repair shop can only handle a certain number of robots at a time. The goal is to minimize the total distance traveled by all robots to get them fixed and back to work. This problem is akin to planning a carpool for a group of friends who want to minimize their travel distance to a concert.